剑指 Offer II 053. 二叉搜索树中的中序后继

,

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    private static class State {
        private TreeNode pre;
        private TreeNode succ;
    }

    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        State state = new State();
        dfs(state, root, p);
        return state.succ;
    }

    private void dfs(State state, TreeNode node, TreeNode p) {
        if (node == null || state.succ != null) {
            return;
        }

        dfs(state, node.left, p);
        if (state.pre == p) {
            state.succ = node; // 注意此处不能 return, 否则 pre 指针不能被更新，会导致 succ 被覆盖
        }
        state.pre = node;
        dfs(state, node.right, p);
    }
}

Binary Search Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode node = root;
        TreeNode successor = null;
        while (node != null) {
            if (node.val > p.val) {
                successor = node;
                node = node.left;
            } else {
                node = node.right;
            }
        }

        return successor;
    }
}

References

剑指 Offer II 053. 二叉搜索树中的中序后继