LeetCode Top Interview Questions 285. Inorder Successor in BST (Java版; Medium)

梦里梦外; 2023-07-03 12:07 29阅读 0赞

### [welcome to my blog][] ###

## LeetCode Top Interview Questions 285. Inorder Successor in BST (Java版; Medium) ##

#### 题目描述 ####

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.
    
    The successor of a node p is the node with the smallest key greater than p.val.
    
    Example 1:

![format_png][]

Input: root = [2,1,3], p = 1
    Output: 2
    Explanation: 1's in-order successor node is 2. Note that both p and the return value is of TreeNode type.
    
    Example 2:

![format_png 1][]

Input: root = [5,3,6,2,4,null,null,1], p = 6
    Output: null
    Explanation: There is no in-order successor of the current node, so the answer is null.
    
    
    Note:
    
    If the given node has no in-order successor in the tree, return null.
    It's guaranteed that the values of the tree are unique.

#### 第一次做; 利用BST的性质定位节点: 左子树的数都比根节点小, 右子树的数都比根节点大; 核心: 注意递归函数的思考方式, 每一个递归函数中root都是根节点, 没有父节点, 也就是仅仅思考以root为根的数 ####

class Solution { 
        public TreeNode inorderSuccessor(TreeNode root, TreeNode p) { 
            //base case 
            if(root==null)
                return null;
            TreeNode res = null;
            //说明后继节点1)要么是root, 2)要么在root的左子树上
            //如果roo.val>p.val, 那么后继节点要么是root, 要么在root的左子树上
            if(root.val > p.val){ 
                res = inorderSuccessor(root.left, p);
                return res == null ? root : res;
            }
            //如果root.val==p.val, 说明后继节点是root的父节点; 这么思考是错误的! 应该把root当成根节点, 没有父节点; 所以说如果root.val<=p.val, 那么后继节点一定在root的右子树上
            //如果root.val<p.val, 说明后继节点在root的右子树上
            
            //上面的思考是错误的! 应该把root当成根节点, 没有父节点; 所以说如果root.val<=p.val, 那么后继节点一定在root的右子树上
            //上面的思考是错误的! 应该把root当成根节点, 没有父节点; 所以说如果root.val<=p.val, 那么后继节点一定在root的右子树上
            //上面的思考是错误的! 应该把root当成根节点, 没有父节点; 所以说如果root.val<=p.val, 那么后继节点一定在root的右子树上
            else{ 
                return inorderSuccessor(root.right, p);
            }
        }
    }

#### 第一次做; 参考了题解, 利用BST的性质: 左子树的值都比根小, 右子树的值都比根大, 这个性质能很好地定位某个节点 ####

//迭代的方法; 这个方法非常巧妙
    class Solution { 
        public TreeNode inorderSuccessor(TreeNode root, TreeNode p) { 
            //之所以要初始化为null, 是为了解决p是最右节点时的情况
            TreeNode res = null;
            while(root!=null){ 
                //如果root.val > p.val, 说明后继节点1)要么是root 2)要么在root的左子树上
                if(root.val > p.val){ 
                    res = root;
                    root = root.left;
                }
                //如果root.val <= p.val, 说明后继节点1)要么在root的右子树上 2)如果root.right是null, 说明res就是p的后继节点
                else{ 
                    root = root.right;
                }
            }
            return res;
        }
    }

#### 第一次做; 中序遍历, 递归, 左根右; 开始写错了, 把处理root的代码放到了base case中, 这样就不能保证root是大于p的节点中值最小的节点了 ####

class Solution { 
        //递归逻辑: 返回中序遍历中p的后继节点
        public TreeNode inorderSuccessor(TreeNode root, TreeNode p) { 
            //base case
            if(root==null)
                return null;
            //左
            TreeNode leftRes = inorderSuccessor(root.left, p);
            if(leftRes!=null)
                return leftRes;
            //根
            if(root.val>p.val)
                return root;
            //右
            TreeNode rightRes = inorderSuccessor(root.right, p);
            return rightRes;
        }
    }

[welcome to my blog]: https://littlehaes.com
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS8yOGE0OGE3NTE3ODJhOTRiMTQzYjUxNGI2MmQ4MjMzNC94bWxub3RlLzhCM0I5NTYwOTFDRTQ2NjlCQTdFQUEzNTQ5MTlGQjI2LzU4MjUx?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS8yOGE0OGE3NTE3ODJhOTRiMTQzYjUxNGI2MmQ4MjMzNC94bWxub3RlL0MxQjRCQkIwNzM2QjQ3QUI4MjM1Njg5NUU5QkJCNEMwLzU4MjU0?x-oss-process=image/format,png