找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

楼主: jbao
收起左侧

[Google] 一道google面试题:find Kth node in BST

  [复制链接]

3

主题

2

精华

106

积分

资深会员

Rank: 2

积分
106
发表于 12-1-2014 06:18 PM | 显示全部楼层
可以用一个inorder traversal解决,可以设置while判断条件,当到第k个的时候停止

4

主题

2

精华

113

积分

资深会员

Rank: 2

积分
113
 楼主| 发表于 12-1-2014 09:31 PM | 显示全部楼层
WanderWen 发表于 12-1-2014 06:18 PM
+ c+ c2 s# C) s4 Q可以用一个inorder traversal解决,可以设置while判断条件,当到第k个的时候停止
# G" e/ ~0 \# s0 R
确实,这样就是in order的变种。 不过我觉得没必要用list把之前遍历的记录,只需要有一个count就行
; r( s! q  F% l2 \6 j
2 C8 i6 L# Z3 o5 W& i* ]
  1.         public static int findKth(TreeNode root, int k) {
    0 t5 @2 Y  A9 W, M( R+ H
  2.                 if (root == null) {9 `7 i6 \7 d5 \# v- o& B
  3.                         return -1;5 h+ Z' q( C" N4 M9 `
  4.                 }
    $ _! d  ?3 f/ A  @- |3 }
  5.                 int count = 0;
    1 b, J8 C: B) K1 t9 N/ U! S% v& @% T' h
  6.                 Stack<TreeNode> stack = new Stack<TreeNode>();! k! \( I: K2 a! u$ |* }
  7.                 while (!stack.isEmpty() || root != null) {" B" e" {! L4 n! O1 h) U# j
  8.                         if (root != null) {
    1 G. s9 k9 C' z$ v3 @
  9.                                 stack.push(root);' E9 i  e3 |( q# i& _
  10.                                 root = root.left;+ C# V' [4 P2 G: B
  11.                         } else {
    + L1 K6 H9 R5 y9 B0 b- b# D
  12.                                 TreeNode node = stack.pop();: x# H" ~: \- b9 F: K. b" b
  13.                                 if (++count == k) {
    ; x5 h) Z" K- V1 |) J0 t, H
  14.                                         return node.val;
    6 S& o0 I9 f! V, V9 C
  15.                                 }
    8 Y' @* O; e" M4 A
  16.                         }* N5 D& |" O7 ^' e8 w; i# i* L
  17.                 }
    6 }4 K. I2 |  W1 W! A
  18.                 return -1;/ |+ t# f6 `. f- t
  19.         }
复制代码

2

主题

2

精华

139

积分

资深会员

Rank: 2

积分
139
发表于 12-1-2014 10:08 PM | 显示全部楼层
如果这个function要被调用很多次,是不是应该用一个算法导论里讲的 Order-Statistic tree? 这样每次找到rank为k的节点的时间复杂度就是O(lgn).
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表