找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

楼主: jbao
收起左侧

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

  [复制链接]

17

主题

10

精华

340

积分

高级会员

Rank: 3Rank: 3

积分
340
发表于 1-23-2015 07:31 PM | 显示全部楼层
jbao 发表于 12-1-2014 09:31 PM7 w  m6 }; i" T$ I( K
确实,这样就是in order的变种。 不过我觉得没必要用list把之前遍历的记录,只需要有一个count就行
  e9 m+ v, [: y5 q
u're right.

32

主题

10

精华

499

积分

高级会员

Rank: 3Rank: 3

积分
499
发表于 1-25-2015 01:35 PM | 显示全部楼层
我的挫code
  1.         public TreeNode kthNode(TreeNode root, int k){                        4 ?: {1 A1 ?3 m
  2.                 int count = 0;' s- @  Z; l/ f9 ?. c; Q* F
  3.                 Stack<TreeNode> nds = new Stack<TreeNode>();2 ]" S: q9 f/ _1 F! g5 C' D
  4.                 TreeNode curr = root, kth = null;3 I" i6 Q, m  l* J
  5.                 while(!nds.empty() || curr != null) {
    ! }/ R) U' X3 k5 L' u* ?
  6.                         if(curr != null) {
    6 H1 Z* s7 R# \) H
  7.                                 nds.push(curr);7 Q, P. P) N0 K+ w& q5 c+ G
  8.                                 curr = curr.left;
    ' Y  {* e8 r% d9 F. I3 B4 P5 c0 R4 m
  9.                         } else {- j  p0 ?- x+ Q2 U! n
  10.                                 curr = nds.pop();
    ; T. n0 T' ^+ `
  11.                                 ++count;3 {2 W+ h& E* g* `
  12.                                 if(count == k) {
    0 Y) v, u$ Q- W- e! o
  13.                                         kth = curr;
    : W* x1 Y" u3 w( ^5 q
  14.                                         break;  c5 d% x4 u" I/ O$ x' l9 {/ L! f+ T
  15.                                 }( U, V3 k1 i# e; }
  16.                                  ! [0 M; G- a$ E2 N  w& I) R" r  q
  17.                                 curr = curr.right;                       
    : S9 Y3 y) M2 ^7 A5 g6 w0 m
  18.                         }
    0 r' x! v' n" I6 u) [# j
  19.                 }
    0 G! d# |8 i+ m# L2 {1 x
  20.                 ' z: [7 j; u- X, }" R, |: v$ q
  21.                 return kth;       
    ; w; [  u, `2 ?1 B9 |" g$ O! k
  22.         }
复制代码

4

主题

0

精华

27

积分

新米人

Rank: 1

积分
27
发表于 2-1-2015 03:10 PM | 显示全部楼层
jbao 发表于 12-1-2014 09:31 PM
" F& g+ _7 I0 D) O# e确实,这样就是in order的变种。 不过我觉得没必要用list把之前遍历的记录,只需要有一个count就行

* X3 ^4 M$ \+ Q  z算法挺不错,不过好像漏了root=root.right;
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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