二叉搜索树中的中序后继 II

510. 二叉搜索树中的中序后继 II

给定一棵二叉搜索树和其中的一个节点 node ，找到该节点在树中的中序后继。如果节点没有中序后继，请返回 null 。

一个节点 node 的中序后继是键值比 node.val 大所有的节点中键值最小的那个。

你可以直接访问结点，但无法直接访问树。每个节点都会有其父节点的引用。节点 Node 定义如下：

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
}

示例 1：

输入：tree = [2,1,3], node = 1
输出：2
解析：1 的中序后继结点是 2 。注意节点和返回值都是 Node 类型的。

示例 2：

输入：tree = [5,3,6,2,4,null,null,1], node = 6
输出：null
解析：该结点没有中序后继，因此返回 null 。

示例 3：

输入：tree = [15,6,18,3,7,17,20,2,4,null,13,null,null,null,null,null,null,null,null,9], node = 15
输出：17

示例 4：

输入：tree = [15,6,18,3,7,17,20,2,4,null,13,null,null,null,null,null,null,null,null,9], node = 13
输出：15

示例 5：

输入：tree = [0], node = 0
输出：null

提示：

树中节点的数目在范围 [1, 10⁴] 内。
-10⁵ <= Node.val <= 10⁵
树中各结点的值均保证唯一。

进阶：你能否在不访问任何结点的值的情况下解决问题?

相似题目

二叉搜索树中的中序后继

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

/* // Definition for a Node. class Node { public: int val; Node* left; Node* right; Node* parent; }; */ class Solution { public: Node* inorderSuccessor(Node* node) { } };

golang 解法, 执行用时: 8 ms, 内存消耗: 6.1 MB, 提交时间: 2023-10-22 10:44:45

/**
 * Definition for Node.
 * type Node struct {
 *     Val int
 *     Left *Node
 *     Right *Node
 *     Parent *Node
 * }
 */

func inorderSuccessor(node *Node) (ans *Node) {
    root := node
    for root.Parent!=nil {
        root=root.Parent
    }
    for root!=nil {
        if root.Val>node.Val {
            ans=root
            root=root.Left
        } else {
            root=root.Right
        }
    }
    return
}

cpp 解法, 执行用时: 24 ms, 内存消耗: 11.8 MB, 提交时间: 2023-10-22 10:44:24

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* parent;
};
*/

class Solution {
public:
    Node* inorderSuccessor(Node* node) {
        if (node->right)        //有右子 右子树的最左下
        {
            node = node->right;
            while (node->left)
                node = node->left;
            return node; 
        }
        else
        {
            while(node->parent && node == node->parent->right)
                node = node->parent;
            return node->parent;        //是父结点的左子了  返回父结点
        }
        
    }
};

python3 解法, 执行用时: 68 ms, 内存消耗: 23.5 MB, 提交时间: 2023-10-22 10:44:03

"""
# Definition for a Node.
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None
"""

class Solution:
    def inorderSuccessor(self, node: 'Node') -> 'Node':
        if node.right:          #有右子 则是右子树的最左下
            node = node.right
            while node.left:
                node = node.left
            return node
        else:
            while node.parent and node.parent.right == node:
                node = node.parent
            return node.parent

java 解法, 执行用时: 32 ms, 内存消耗: 42.9 MB, 提交时间: 2023-10-22 10:43:41

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
};
*/

class Solution {
    public Node inorderSuccessor(Node x) {
        if (x.right != null) {
            // 有右子树，则后继在树的相对较低的地方，往下走，尽量往右子树的左边走
            x = x.right;
            while (x.left != null) x = x.left;
            return x;
        }else {
            // 没有右子树,则后继在树的相对较高的地方，往上找
            // 直到找到一个祖宗节点 tmp，它是它父节点的左子节点
            while (x.parent != null && x == x.parent.right) x = x.parent;
            // x.parent == null 或 x == x.parent.left
            return x.parent;    
        }
    }
}

上一题

下一题

详情