Facebook Interview Question for

妮可

Given two pre-order traversal arrays of two binary search tree respectively, find first pair of non-matching leaves.
Follow Up: If they are general binary trees instead of BSTs, could you solve it? give out your reason. ; o( g) D. F. ?/ k& m
% k3 V7 I1 Y: }$ D, H- r; C5 N1 Q, j
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.

弱弱求offer

@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.

爸爸回来了

def get_leaves(pre_order, leaves):
8 T% Y9 r  c2 D: I7 D( G    if not pre_order:
        return
    
    root = pre_order[0]
1 _. _  }  r) C* {/ e/ ~: N% Y    if len(pre_order) == 1:
* Q9 |6 `) f  K& I8 H        leaves.append(root)
        return
        
9 E; C- Z% m  T    left_start = None
# |2 l- p9 _6 `6 _1 E% e. f1 `: D    left_end = None
' r9 ^! G) d! j1 {8 d    right_start = None
: i2 \& j( O- W+ R7 k    righ_end = None
0 M' F& ^, _' z( X    for i in xrange(1, len(pre_order)):
, h0 y  K% i. [1 `- l: o/ w8 l        if not left_start and pre_order[i] <= root:
            left_start =  i
, N! Z6 K% s  ]- b8 C        
        if not right_start and pre_order[i] > root:
            right_start =  i
3 o/ \& _; Y7 Z" p( p    
    if left_start:
9 W; A& V; X! G5 B+ b3 A& u* x( F        if right_start: left_end = right_start
        else: left_end = len(pre_order)
        get_leaves(pre_order[left_start:left_end], leaves)
    
    if right_start:
        right_end = len(pre_order)
/ j4 f2 O$ j( @3 T' t0 Z2 t        get_leaves(pre_order[right_start:right_end], leaves)

. t/ c2 @0 I% S) ]a = [5, 3, 2, 1, 4, 7, 6, 8]
a_leaves =[]
" i0 G$ u- }% lget_leaves(a, a_leaves)
print a_leaves