利用二叉查找树中序遍历有序的特点。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private static int k1, res;
public int kthLargest(TreeNode root, int k) {
k1 = k;
// 中序遍历(递增) 左根右
dfs(root);
return res;
}
private static void dfs(TreeNode root) {
if(root == null || k1 == 0)
return;
// 第k大倒序
// 右
dfs(root.right);
// 根
if(--k1 == 0)
res = root.val;
// 左
dfs(root.left);
}
}
题目描述 给定一棵二叉搜索树,请找出其中的第k小的结点。例如, (5,3,7,2,4,6,8) 中,按结点数值大小顺序第三小结点的值为4。
private TreeNode ret;
private int cnt = 0;
public TreeNode KthNode(TreeNode pRoot, int k) {
inOrder(pRoot, k);
return ret;
}
private void inOrder(TreeNode root, int k) {
if (root == null || cnt >= k)
return;
inOrder(root.left, k);
cnt++;
if (cnt == k)
ret = root;
inOrder(root.right, k);
}