找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 3798|回复: 15
收起左侧

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

  [复制链接]

4

主题

2

精华

113

积分

资深会员

Rank: 2

积分
113
发表于 12-1-2014 04:34 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
最近看到google有个面经题,find kth node in BST. 想问下,一般面试中 允许写wrapper class吗?我这样写在面试中有什么问题吗?
. |& Q5 v1 q( c6 h1 C" t; _- m# q$ X, l( p6 \; I4 e. a6 i
  1.         static class Wrapper {
    7 K0 |0 f4 p+ d8 ^8 x9 Q- G4 L
  2.                 int count = 0;
    : M# V( W, h  D# l8 J
  3.                 int num = 0;
    ! b7 _: Y  O9 n4 F
  4.         }7 x4 i# ^8 k9 o" {4 ~
  5. , n9 k& L6 c1 X! x. Y! b
  6.         public static int findKthNode(TreeNode node, int k) {
    3 i$ o/ e8 i1 B/ u+ f
  7.                 Wrapper wrapper = new Wrapper();
    : O" B4 c) P& z, b0 e
  8.                 if (find(node, k, wrapper)) {
    # W, n) X: k. J, m' m4 R3 |
  9.                         return wrapper.num;  ^/ t/ w; s) r9 l6 h! t
  10.                 }/ K- E0 s, p& L
  11.                 return -1;
    ; q* J1 L" [1 P! ?
  12.         }% Q1 j+ C2 T7 ]0 e2 t+ C' D
  13. 6 |$ U* w- V4 j: U" e
  14.         public static boolean find(TreeNode node, int k, Wrapper wrapper) {
    + i6 n. e1 p* N; X% ~
  15.                 if (node == null) {
    ' H2 A4 U. l) Q3 A, ?
  16.                         return false;
    0 n! p: E0 N+ |+ G8 ~& p& |
  17.                 }& D( m) r8 v! }) F3 s6 N1 ^
  18.                 boolean res = find(node.left, k, wrapper);
    " A+ L7 H7 ^3 q/ ^) x
  19.                 if (res) {
    ; R* e) d& r# D8 ^5 L' ~/ B
  20.                         return true;
    9 @- Q4 v/ a5 ^2 Z1 {/ f
  21.                 }
    / v+ ?1 C; K, v8 |% R/ X% C: @$ R) }
  22.                 wrapper.count++;- j- ^1 ?& g3 P0 M
  23.                 if(wrapper.count == k){. C5 m9 l8 \% |: ~' f* p5 b
  24.                         wrapper.num = node.val;
    ( ~" S- s( j/ ]9 R( m* Y- q
  25.                         return true;
    ! p4 V4 e, o' t1 |/ G8 K4 y
  26.                 }- s9 ~1 t; p7 c* ~' C% g
  27.                 return find(node.right, k, wrapper);
    3 {8 O& ~7 A. d
  28.         }
复制代码

本帖被以下淘专辑推荐:

3

主题

2

精华

106

积分

资深会员

Rank: 2

积分
106
发表于 12-1-2014 06:17 PM | 显示全部楼层
  1. public int kthBST(TreeNode root) {
      T0 E: P7 O! j
  2.         // recursive solution * M* l( {$ W7 Q- Q/ U' Y
  3.         List<Integer> res = new LinkedList<Integer>(); , p, ^, f6 B' A+ E6 R* t
  4.         if(root==null) return res;
    , T$ r% a- ]: B% X" D& R- Z0 g
  5.         Stack<TreeNode> stack = new Stack<TreeNode>();
    , X; }0 y2 n. S- `5 O; w
  6.         while(!stack.isEmpty() || root!=null){
    8 g! d# U8 j4 M) {1 L! h5 a
  7.             if(root!=null){
    / O+ {8 s# E1 ?4 G3 }- r
  8.                 stack.push(root);
    / E5 q, J* \. M  ?
  9.                 root = root.left; + ]1 ]- M' ~9 u
  10.             }else{
    9 t& R4 a3 ]. z
  11.                 root = stack.pop();
      K1 r9 }8 t4 J* }) ^( ]
  12.                 res.add(root.val); . \  }# a/ v  o- J% ~
  13.                 root = root.right;
    2 f' E* Y% R* O0 C" Y# S
  14.             }
    : d% V: k( b# t9 K( ~" c$ |0 M
  15.         }
    & ]  Q) q3 C1 h9 Q2 z3 n8 W: J
  16.         return res.get(k-1); 8 c- ?3 |5 a, r
  17.     }
复制代码
回复 支持 1 反对 0

使用道具 举报

3

主题

2

精华

106

积分

资深会员

Rank: 2

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

使用道具 举报

发表于 12-1-2014 05:43 PM | 显示全部楼层
允许吧。。。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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