本文共 1677 字,大约阅读时间需要 5 分钟。
找出BST中的第k个节点值
BST的中序遍历就是一个升序数组啊!!!!
数左子树中节点个数num,如果是k - 1个,那么当前root即为所求;如果num大于k,则从左子树中找第k个;否则从右子树中找第k - 1 - num个(即减去左子树中节点个数以及root这一个)
public class Solution { public int kthSmallest(TreeNode root, int k) { int num = count(root.left); if (num >= k) { return kthSmallest(root.left, k); } else if (num + 1 < k) { // 注意第二个参数 return kthSmallest(root.right, k - 1 - num); } return root.val; } private int count(TreeNode root) { if (root == null) { return 0; } return 1 + count(root.left) + count(root.right); }}
注意dfs的时候函数调用的时候就要保证root不是null,这样里面就不用判断了
递归二叉树的中序遍历
public class Solution { int count = 0; int num = 0; public int kthSmallest(TreeNode root, int k) { count = k; dfs(root); return num; } private void dfs(TreeNode root) { if (root.left != null) { dfs(root.left); } count--; if (count == 0) { num = root.val; return; } if (root.right != null) { dfs(root.right); } }}
非递归二叉树的中序遍历
public class Solution { public int kthSmallest(TreeNode root, int k) { Stackstack = new Stack(); TreeNode cur = root; while (cur != null || !stack.isEmpty()) { while (cur != null) { stack.push(cur); cur = cur.left; } if (!stack.isEmpty()) { cur = stack.pop(); k--; if (k == 0) { return cur.val; } cur = cur.right; } } return -1; }}
转载地址:http://rahld.baihongyu.com/