《剑指 Offer》专项突破版 - 面试题 53 : 二叉搜索树的下一个节点（详解 C++ 实现的两种方法）

目录

前言

一、方法一

二、方法二

前言

题目链接：LCR 053. 二叉搜索树中的中序后继 - 力扣（LeetCode）

题目：

给定一棵二叉搜索树和它的一个节点 p，请找出按中序遍历的顺序该节点 p 的下一个节点。假设二叉搜索树中节点的值都是唯一的。例如，在下图的二叉搜索树中，节点 8 的下一个节点是节点 9，节点 11 的下一个节点是 nullptr。

一、方法一

解决这个问题的最直观的思路就是采用二叉树的中序遍历。可以用一个布尔变量 isFound 来记录是否已经遍历到节点 p。该变量初始化为 false，遍历到节点 p 就将它设为 true。在这个变量变为 true 之后遍历到的第 1 个节点就是要找的节点。基于这种思路可以编写出如下所示的代码：

class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        stack<TreeNode*> st;
        bool isFound = false;
        TreeNode* cur = root;
        while (cur || !st.empty())
        {
            while (cur)
            {
                st.push(cur);
                cur = cur->left;
            }
​
            cur = st.top();
            st.pop();
            if (isFound)
                break;
            else if (cur == p)
                isFound = true;
            cur = cur->right;
        }
        return cur;
    }
};

该算法的时间复杂度是 O(n)，空间复杂度是 O(h)，h 为二叉搜索树的深度。

二、方法二

二叉搜索树中节点 p 的中序遍历下一个节点是所有大于节点 p 的值中值最小的节点。例如，在上图的二叉搜索树中，有 3 个节点的值比节点 8 的值大，分别是节点 9、节点 10 和节点 11，并且节点 9 是 3 个节点中值最小的。

下面按照在二叉搜索树中根据节点的值查找节点的思路来分析。从根节点开始，每到达一个节点就比较根节点的值和节点 p 的值。

1. 当前节点的值小于或等于节点 p 的值，那么节点 p 的下一个节点应该在它的右子树。

2. 如果当前节点的值大于节点 p 的值，那么当前节点有可能是它的下一个节点。此时当前节点的值比节点 p 的值大，但节点 p 的下一个节点是所有大于它的节点中值最小的一个，因此接下来前往当前节点的左子树，确定是否能找到值更小但仍然大于节点 p 的值的节点。

重复这样比较，直至找到最后一个大于节点 p 的值的节点，就是节点 p 的下一个节点。

class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        TreeNode* cur = root;
        TreeNode* result = nullptr;
        while (cur)
        {
            if (cur->val <= p->val)
            {
                cur = cur->right;
            }
            else
            {
                result = cur;
                cur = cur->left;
            }
        }
        return result;
    }
};

该算法的时间复杂度是 O(h)，空间复杂度是 O(1)。