LeetCode 285 & 510. 二叉树中序后继 I & II

题目详见：LettCode 285. Inorder Successor in BST

解法一

思路

由于从根节点开始，我们可以利用中序遍历的迭代写法，并加入一个 prev 节点记录上一次访问的节点。当上一次访问的节点值和目标节点值相同时，当前遍历的节点就是我们要找的后继。

代码

class Soution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if (root == null) return null;

        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        TreeNode prev = null;
        while (!stack.isEmpty() || curr != null) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            if (prev != null && prev.val == p.val) {
                return curr;
            }
            prev = curr;
            curr = curr.right;
        }
        return null;
    }
}

复杂度分析

• 时间复杂度
  • O(H) 遍历整个树
• 空间复杂度
  • O(H) to keep the stack

题目详见：510. Inorder Successor in BST II

解法一

思路

这道题没有从根节点出发，而是需要直接找出一个节点的后继。此时要分两种情况讨论。

因为中序遍历的顺序是 左 - 根 - 右，所以如果目标节点有右孩子，我们先将指针移动到右孩子，随后一直寻找该节点的左孩子，直到没有左孩子为止。
如果目标节点没有右孩子，那么需要一直向上回溯，直到找到一个节点，是父节点的左孩子，那么这个父节点就是后继。

代码

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

            while (node.left != null) {
                node = node.left;
            }

            return node;
        }

        while (node.parent != null && node == node.parent.right) {
            node = node.parent;
        }

        return node.parent;
    }
}

复杂度分析

• 时间复杂度 O(H)
• 空间复杂度 O(1)

TakeAway

• 第二题不知道这个节点在那个位置，所以需要针对 inorder traversal 的性质来解题。

本作品采用《CC 协议》，转载必须注明作者和本文链接