【LeetCode刷题记录】33.后继者

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

一、题目描述：

题目来源：LeetCode-后继者

设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。

如果指定节点没有对应的“下一个”节点，则返回null。

示例 1:

输入: root = [2,1,3], p = 1

  2
 / \
1   3
复制代码

输出: 2

示例 2:

输入: root = [5,3,6,2,4,null,null,1], p = 6

      5
     / \
    3   6
   / \
  2   4
 /   
1
复制代码

输出: null

二、思路分析：

中序遍历，利用一个tag记录是否找到了目标p。

一直往左找，并依次加入栈，直到为空。

root=root.left 出栈，并判断tag是否为true，如果为true，代表已经找到了p的下一个，直接返回

否则继续判断是否为目标p，如果为p,将tag置为true。

遍历出栈元素的右节点。root=root.right

三、AC 代码：

    class Solution {
        public static TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
            Deque<TreeNode> nodeDeque = new ArrayDeque<>();
            boolean findFlag = false;
            while (root != null || !nodeDeque.isEmpty()) {
                if (root != null) {
                    nodeDeque.addFirst(root);
                    root = root.left;
                } else {
                    root = nodeDeque.pollFirst();
                    if (findFlag) {
                        return root;
                    }
                    if (root.val == p.val) {
                        findFlag = true;
                    }
                    root = root.right;
                }
            }
            return null;
        }
    }

复制代码

时间复杂度：O(n)

代码演进：

    class Solution {

        TreeNode previousNode = null;
        TreeNode result = null;

        public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
            if (root == null || p == null) {
                return result;
            }
            inorder(root, p);
            return result;
        }

        private void inorder(TreeNode root, TreeNode previous) {
            if (root == null) {
                return;
            }
            inorder(root.left, previous);
            if (previousNode == previous) {
                result = root;
            }
            previousNode = root;
            inorder(root.right, previous);
        }
    }
复制代码

四、总结：

二叉搜索树的中序遍历是 递增序列

p.val > root.val : 进入root 的右子树

p.val < root.val : 进入root 的左子树

如果相等:

判断是否存在右子树:

存在, 其右子树的最左节点,就是 后继者, 比p.val 大的最小节点

不存在, 则是其父节点(pre_root)

递归搜索的时候,把父节点(pre_root) 同步传下来, 相等的时候做个判断

预设 根节点的父节点为 None, 进入右子树的时候,如果没有右子树,pre是None,也符合