入门力扣自学笔记34 C++ （题目编号：面试题04.06）

面试题 04.06. 后继者

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

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

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

  2
 /
1   3

输出: 2

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

      5
     /
    3   6
   /
  2   4
 /   
1

输出: null

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/successor-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题就是采用两个结点，一个表示前结点，一个表示当前结点，采用中序遍历的方式，当前结点等于目标结点的时候，那么当前的这个结点就是我们要找的中序后继。

class Solution {
public:
    TreeNode* ans;
    TreeNode* pre;

    bool find(TreeNode* cur,TreeNode* tar)
    {
        if(cur->left && find(cur->left,tar))
        {
            return true;
        }
        if(pre == tar)
        {
            ans = cur;
            return true;
        }
        pre = cur;
        if(cur->right && find(cur->right,tar))
        {
            return true;
        }
        return false;
    }

    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        pre = NULL;
        ans = NULL;
        find(root,p);
        return ans;
    }
};