leetcode 链接：后继者

题目

设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。
如果指定节点没有对应的“下一个”节点，则返回 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

解答 & 代码

解法一

中序遍历，如果当前遍历到的节点 root 的前驱节点 pre 就是指定节点 p，那么当前节点 root 就是指定节点 p 的后继节点。

• 注意：递归中序遍历函数 inOrderProcess(TreeNode* root, TreeNode* p, TreeNode*& pre, TreeNode*& next) 中 pre、next 都是需要修改的值，因此需要加上引用符 &

  /**
  * 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 {
  private:
    void inOrderProcess(TreeNode* root, TreeNode* p, TreeNode*& pre, TreeNode*& next)   // pre、next 都要加引用
    {
        // 递归结束条件：当前节点为空，or 已经找到指定节点 p 的后继节点（next 不为空）
        if(root == NULL || next != NULL)
            return;
  
        inOrderProcess(root->left, p, pre, next);   // 先递归遍历左子树
  
        if(pre == p)    // 如果当前节点（root）的前驱节点为指定节点 p，那么当前节点（root）就是答案
            next = root;
        pre = root;     // 更新前驱节点
  
        inOrderProcess(root->right, p, pre, next);  // 再递归遍历右子树
    }
  public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {     
        TreeNode* pre = NULL;   // 中序遍历的前驱节点
        TreeNode* next = NULL;  // 中序遍历的后继节点，用于存储本题答案（即指定节点 p 的后继节点）
        inOrderProcess(root, p, pre, next);
        return next;
    }
  };
  

  执行结果： ``` 执行结果：通过

执行用时：52 ms, 在所有 C++ 提交中击败了 10.41% 的用户 内存消耗：22.4 MB, 在所有 C++ 提交中击败了 37.72% 的用户 ```

解法二

利用二叉搜索树的特性：二叉搜索树的中序遍历，就是按升序访问节点