X

LEETCODE 285. Inorder Successor in BST 解题思路分析

题目大意:

二叉搜索树中的顺序后继

给你一个二叉搜索树和其中的某一个结点,请你找出该结点在树中顺序后继的节点。

结点 p 的后继是值比 p.val 大的结点中键值最小的结点。

示例 1:

输入: root = [2,1,3], p = 1 
输出: 2 
解析: 这里 1 的顺序后继是 2。请注意 p 和返回值都应是 TreeNode 类型。 

示例 2:

输入: root = [5,3,6,2,4,null,null,1], p = 6 
输出: null 
解析: 因为给出的结点没有顺序后继,所以答案就返回 null 了。 

注意:

  1. 假如给出的结点在该树中没有顺序后继的话,请返回 null
  2. 我们保证树中每个结点的值是唯一的

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=285

解题思路分析:

题目要找到一个节点,该节点是大于p的所有节点中最小的那个。首先考虑BST中哪些节点大于p:

  1. p的右子节点都大于p。
  2. 从节点p向上寻找根节点,如果p是该根节点的左子节点,那么该根节点大于p。

接下来,考虑所有大于p的节点中,哪个是最小的,根据上面2条结果:

  1. 由于p的右子树中的节点都大于p,那么右子树中最小的一定是该子树最左边的元素。
  2. 距离p最近的根节点,并且p是该根节点的左子树中的节点。

对于上述1和2两个节点,由于节点p和节点p的右子树都是2中描述的根节点的左子节点,所以结果2一定大于结果1,因为取所有大于p中的最小值,因此优先返回结果1,即p的右子树中最靠左的元素,如果p的右子树为空,则需要返回结果2的根节点。

实现代码:

public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
    // 递归求解
    return help(root,null,p.val);
}
// root:当前节点
// parent: 距离当前节点最近的根节点,并且p是该根节点左子树中的元素
// target:目标节点p的值
TreeNode help(TreeNode root, TreeNode parent, int target){
    // 如果target大于当前节点,在当前节点的右子树中继续寻找
    // 由于当前节点小于右子树中的值,parent不变
    if(target>root.val){
        return help(root.right,parent,target);
    }
    // 如果target小于于当前节点,在当前节点的左子树中继续寻找
    // 由于当前节点大于左子树中的值,parent为当前节点
    else if(target<root.val){
        return help(root.left,root,target);
    }
    // 以下为当前节点是P的情况

    // 如果右节点不为空,返回右子树中最小的元素
    if(root.right!=null) return findMin(root.right);
    // 如果右节点为空,返回parent
    else return parent;
}
// 找到当前节点中最靠左的子节点
TreeNode findMin(TreeNode root){
    if(root.left==null) return root;
    return findMin(root.left);
}

本题解法执行时间为2ms。

Runtime: 2 ms, faster than 100.00% of Java online submissions for Inorder Successor in BST.

Memory Usage: 46.5 MB, less than 5.26% of Java online submissions for Inorder Successor in BST.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-285-inorder-successor-in-bst-解题思路分析/
Categories: leetcode
kwantong: