给定一棵二叉搜索树,请找出其中的第k个的节点(按节点的数值大小顺序)。
分析
如果按照中序遍历的顺序遍历一棵二叉搜索树,遍历序列的数值是递增排序的。
实现
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 36 37 38 39
|
public class { class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } public TreeNode findKth(TreeNode root, int k){ if (root == null || k == 0) return null; count = k; return doFindKth(root); } private int count; private TreeNode doFindKth(TreeNode root){ TreeNode target = null; if (root.left != null) target = doFindKth(root.left); if (target == null){ if (count == 1) target = root; else count--; } if (target == null && root.right != null) target = doFindKth(root.right); return target; } }
|
近期评论