剑指 Offer 54. 二叉搜索树的第k大节点 发表于 2022-04-28 DFS1234567891011121314151617class 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); } }} DFS1234567891011121314151617181920212223242526272829303132333435class 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); } }} Iterate12345678910111213141516171819202122class 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(); }} Reference剑指 Offer 54. 二叉搜索树的第k大节点