题目：力扣挂了。。蛋疼

题目内容后续再补上Html版的

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

题解

按照题意，找的就是二叉树按照中序遍历，排在目标节点后面一位的数字，这个节点可能是目标节点的右子节点，也还有可能是目标节点的父节点（当目标节点作为父节点的左子节点，且没有右子节点的时候）。

所以按照题意，直接DFS写个中序遍历，找到目标节点后，标记下已经找到目标节点，而在遍历下一个节点之前判断下，是否已经找到目标节点，如果已经找到了目标节点，则此时需要遍历的节点便是后继者节点。

class Solution {

    private TreeNode current;
    private TreeNode follower;

    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        midFetch(root,p);
        return follower;
    }

    private void midFetch(TreeNode root , TreeNode p){
        if (root==null)return;
        if (follower!=null){
            return ;
        }
        midFetch(root.left,p);
        if (follower!=null){
            return ;
        }
        if (current!=null && current.val == p.val ){
            follower = root;
            return ;
        }
        current = root;
        midFetch(root.right,p);
    }
}
//leetcode submit region end(Prohibit modification and deletion)

题中左子节点遍历完成之后需要判断下follower!=null，这里一开始没注意，踩了个坑，在官方给出的测试用例中

测试用例:[5,3,6,2,4,null,null,1]
1

如果没有此处的判断，则会跑出错误的答案。按照规则，应当是每遍历一个节点之后都需要判断。

所以左子节点遍历后需要判断一下，root节点遍历的时候需要判断一下，右子节点遍历的时候也需要判断一下，但是因为右子节点已经在方法结尾，所以省去判断。