描述

给定一棵二叉搜索树和其中的一个节点 p ，找到该节点在树中的中序后继。如果节点没有中序后继，请返回 null 。

节点 p 的后继是值比 p.val 大的节点中键值最小的节点，即按中序遍历的顺序节点 p 的下一个节点。

示例

示例1：
285_example_1.png

  1. 输入：root = [2,1,3], p = 1
  2. 输出：2
  3. 解释：这里 1 的中序后继是 2。请注意 p 和返回值都应是 TreeNode 类型。

示例2：
285_example_2.png

1
2
3
输入：root = [5,3,6,2,4,null,null,1], p = 6
输出：null
解释：因为给出的节点没有中序后继，所以答案就返回 null 了。

提示

  • 树中节点的数目在范围 [1, 104] 内。
  • -105 <= Node.val <= 105
  • 树中各节点的值均保证唯一。

解题思路

解法一

此题我们可以利用二叉树的性质（左子树比节点值小，右子树比节点值大），对二叉树进行搜索，不断寻找 “比 p 大，但比当前节点小” 的节点，这样，就能一直逼近 p 节点的后继节点，直至找到 p 的后继节点。

  1. 如果当前节点 > p , 则记录下当前的节点，继续到当前节点的左子树中寻找。
  2. 如果当前节点 < p , 则继续到当前节点的右子树中寻找。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        // ans : 记录当前比 p 节点大的节点
        TreeNode ans = null;
        // 在二叉搜索树中进行搜索
        while(root != null){
            // 如果当前节点 > p，则更新当前比 p 节点大的节点 ans , 同时去左子树进行搜索
            if(root.val > p.val){
                ans = root;
                root = root.left;
            }else{// 如果当前节点 < p , 则到右子树进行搜索
                root = root.right;
            }
        }
        // 当搜寻结束后，ans 保存的就是最近的比 p 节点大的节点。
        return ans;
    }
}

解法二

思路：对于二叉搜索树，中序遍历的结果就是有序的，所以我们在遍历的时候，当遇见目标值就设定一个标记为 True，当下一次遇到一个比目标值大的节点并且标记为 True 的时候，该节点就一定是目标节点的后继

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    // 访问标志
    private boolean hasVisit;
    TreeNode res;
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        hasVisit = false;
        dfs(root, p);
        return res;
    }

    public void dfs(TreeNode node, TreeNode p) {
        if (node == null) return;
        // 遇到目标节点就将访问标记置为true
        if (node == p) hasVisit = true;
        dfs(node.left, p);
        if (hasVisit && node.val > p.val) {
            // 第一次满足if时，当前节点就是答案
            // 之后的就不是直接后继了，所以将访问标记置为false
            hasVisit = false;
            res = node;
        }
        dfs(node.right, p);
    }
}