剑指 Offer 54. 二叉搜索树的第k大节点

,

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int kthLargest(TreeNode root, int k) {
        List<Integer> numList = new ArrayList<>();
        dfs(numList, root);
        return numList.get(numList.size() - k);
    }

    private void dfs(List<Integer> numList, TreeNode node) {
        if (node.left != null) {
            dfs(numList, node.left);
        }
        numList.add(node.val);
        if (node.right != null) {
            dfs(numList, node.right);
        }
    }
}

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
26
27
28
29
30
31
32
33
34
35
class Solution {
    private static class State {
        private int k;
        private int num;

        public State(int k) {
            this.k = k;
        }
    }

    public int kthLargest(TreeNode root, int k) {
        State state = new State(k);
        dfs(state, root);
        return state.num;
    }

    private void dfs(State state, TreeNode node) {
        // right, root, left

        if (node.right != null) {
            dfs(state, node.right);
        }

        if (state.k == 0) {
            return;
        }
        if (--state.k == 0) {
            state.num = node.val;
        }

        if (node.left != null) {
            dfs(state, node.left);
        }
    }
}

Iterate

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int kthLargest(TreeNode root, int k) {
        // right -> root -> left

        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.right;
            }

            // now: root is null
            TreeNode node = stack.pop();
            if (--k == 0) {
                return node.val;
            }
            root = node.left;
        }

        throw new IllegalArgumentException();
    }
}

References

剑指 Offer 54. 二叉搜索树的第k大节点