【递归】后继者

题目

面试题 04.06. 后继者

---

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

如果指定节点没有对应的“下一个”节点，则返回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

解题

方法一：递归

思路

按照题目模拟，中序遍历并记录上一个节点，如果当前遍历到节点的上一个节点为 p 那么当前节点就是要求的节点。

代码

class Solution {
    TreeNode prev, target, ans;

    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        target = p;
        inorderTraversal(root);
        return ans;
    }

    public void inorderTraversal(TreeNode root) {
        if (root == null) return;
        inorderTraversal(root.left);
        if (prev == target) ans = root;
        prev = root;
        inorderTraversal(root.right);
    }
}

方法一：利用 BST 的特性

思路

由 BST 的特性可知，如果 指定节点(p)有右子树，其右子树的最左子节点就是它的中序后继节点(successor)。

否则也可以根据当前节点(node)值与指定节点(p)值的大小关系确定搜索方向：

• 如果 node.val > p.val，把要求的中序后继节点置为 node ，向左子树(node.left)进行搜索。
• 如果 node.val < p.val，向右子树(node.right)进行搜索。
• 如果 node.val == p.val，说明中序后继节点一定在上一次遍历中被找到了，直接退出循环。

代码

class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode successor = p.right;
        if (successor != null) {
            while (successor.left != null) {
                successor = successor.left;
            }
            return successor;
        }
        TreeNode node = root;
        while (node != null && node != p) {
            if (node.val > p.val) {
                successor = node;
                node = node.left;
            } else node = node.right;
        }
        return successor;
    }
}