找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1386|回复: 14
收起左侧

[Facebook] Facebook Interview Question for

[复制链接]

1116

主题

178

精华

3486

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3486
发表于 9-10-2018 08:38 AM | 显示全部楼层 |阅读模式

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

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

x

Given two pre-order traversal arrays of two binary search tree respectively, find first pair of non-matching leaves. / _0 ?; r% x+ ]1 W6 K% e
Follow Up: If they are general binary trees instead of BSTs, could you solve it? give out your reason. * j ~! A+ B: H3 n3 U* G' U
$ j, D$ b$ H; x$ H7 C
For the first question, I was thinking to construct two BSTs from pre-order traversal then do a leaf-level comparison. Any better solutions are welcome.

1144

主题

147

精华

3369

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3369
发表于 9-10-2018 08:38 AM | 显示全部楼层

@hershi,

Your next item leaf determination only holds true if current is less than the ancestor. If current is greater than the ancestor, then next that is greater than current will always test greater than the ancestor whether it is a leaf or not.

回复 支持 反对

使用道具 举报

1161

主题

184

精华

3664

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3664
发表于 9-10-2018 08:38 AM | 显示全部楼层

def get_leaves(pre_order, leaves):
( q, J! s6 @6 ]    if not pre_order:, L. H  F( |  `* R
        return& F; Z+ Y( c7 m% C
    
) i' R$ @# W8 b* ^6 H% A* e+ f    root = pre_order[0]
) |# S9 O' w" g: O4 u0 j    if len(pre_order) == 1:" j; `3 m3 u* ~* V; Z, U5 S  v
        leaves.append(root)
/ B6 N9 T+ I5 [! b        return
5 u! |3 O; i( ?/ u3 G* A        - ]1 ^: p2 F2 d* o- Z6 f
    left_start = None
3 O& }3 ]% B, J7 C& A) Z    left_end = None/ z# u. _- a$ @9 N" B
    right_start = None
9 p( \; p9 h( W( V2 Q    righ_end = None
# ]0 d5 k% M7 ~    for i in xrange(1, len(pre_order)):: _* K( Q5 D6 H
        if not left_start and pre_order[i] <= root:4 D# F/ q: Z  r# j
            left_start =  i
3 y7 G6 d7 j" H        
) K1 k8 v3 k5 t$ N: e0 f1 u        if not right_start and pre_order[i] > root:
# \" t. m5 q, f9 t9 |) Z+ y            right_start =  i
0 Y/ {% _+ h# M! b. H+ \9 @3 b/ G    
& `+ J3 J6 [1 \. I3 |" g" K    if left_start:, a0 c8 ^, l6 z. t) @0 u
        if right_start: left_end = right_start5 b. Q, J; j9 I: ?
        else: left_end = len(pre_order)
7 E4 R" |0 J. a2 `9 e. C        get_leaves(pre_order[left_start:left_end], leaves)
1 {5 W% f( r' e" }  V2 C    
$ S8 i6 H# x. z7 X! W& k1 d    if right_start:: T2 F! g  F/ @/ v9 w7 g
        right_end = len(pre_order)1 i8 d. c& p4 X7 }
        get_leaves(pre_order[right_start:right_end], leaves). E" y: x6 s% k  G& }

7 N% b9 F+ y8 u6 b+ s2 Va = [5, 3, 2, 1, 4, 7, 6, 8]5 }( N* H$ [0 P; c9 v& ^$ X* h! w
a_leaves =[]
9 [% L+ O1 T+ M  P- l8 M: L3 N( aget_leaves(a, a_leaves)
: [6 P8 X! I  n  ]- r8 kprint a_leaves

回复 支持 反对

使用道具 举报

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

本版积分规则

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