面试题 04.06. 后继者

大家好，我是 @负雪明烛。👈👈 点击关注，优质题解不间断。

题目大意

找出二叉搜索树中，比指定节点大的下一个节点。

解题方法

思路

二叉搜索树的定义：

1. 左子树都比当前节点的值小；
2. 右子树都比当前节点的值大。

我们要找比指定节点p大的下一个节点的，那么有以下可能：

1. 当前节点的值 <= 指定节点的值，即 ，那么一定要在的右子树上找比 大的下一个节点。

   因为我们要找比 p大的节点，而此时 和其左子树都比 小，因此左子树上就不用找了。

当然如果右子树不存在，那么也就找不到结果，返回 。

1. 当前节点的值 > 指定节点的值，即 ，那么比 大的节点可能在 的左子树上，也可能就是 $root$。

我们先尝试在 的左子树中寻找比 大的下一个节点，如果能找到，那么就是结果。

否则当前的 是结果。

递归

在上面的思路中，我们提到了「在左/右子树寻找比 大的下一个节点」，这恰好和题目中所定义的函数 inorderSuccessor(TreeNode* root, TreeNode* p)的意义是一样的，因此我们可以使用「递归」。

从这里也能看出来，我们并不是为了「递归」而「递归」，而是我们把「大问题」拆分成了「小问题」。大、小问题只有数据规模不同，但是都可以用同样的方法处理，因此形成了「递归」。

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
    public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        if (!root) return nullptr;
        if (root->val <= p-> val)
            return inorderSuccessor(root->right, p);
        TreeNode* findLeft = inorderSuccessor(root->left, p);
        return findLeft ? findLeft : root;
    }
};

复杂度

• 时间复杂度：最差为 $O(N)$，是二叉搜索树的节点数。
• 空间复杂度：$O(1)$，没用额外空间。

  总结

1. 二叉搜索树的题目都是套路题目，要么是根据左右子树的大小性质（比如本题），要么考察中序遍历。

我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。
关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

• 在刷题的时候，如果你不知道该怎么刷题，可以看 LeetCode 应该怎么刷？
• 如果你觉得题目太多，想在短时间内快速提高，可以看 LeetCode 最经典的 100 道题。
• 送你一份刷题的代码模板：【LeetCode】代码模板，刷题必会
• 我写的 1000 道 LeetCode 题解，都在这里了，免费拿走。