找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

楼主: 妮可
收起左侧

[Facebook] Facebook Interview Question for

[复制链接]

1141

主题

171

精华

3486

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

You can solve this using a stack and a root value.


You initialize the root as Integer.MIN_VALUE

for each number:
if number less than root -> return false;

if number greater than root -> pop stack until the peek value of the stack is greater than the number, make the last popped value the root, the other popped values are the leafes

push the number on the stack

1178

主题

174

精华

3584

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

With BST pre-order array, leaf node seems to be the element that smaller than next element. Is this assumption correct? If so, we can use this to write two loops for each of the array.

1174

主题

171

精华

3558

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

From a pre-order traversal array of a BST, we can detect leaves by doing a sequential scan of the array with a helper stack (see code below for finding the next leaf). - \: s. w7 V9 X+ l
From there, we can just keep on finding the next leaf in each tree and compare until we find leaves that don't match (or we run out of leaves in one tree before the other; or we just find no mismatches). E' g( R7 ] G8 \7 |9 W2 C* @3 ~
8 ~9 v& ~- X' P- K. R
A binary tree with pre-order traversal array of 1,2,3 can be a root of 1 with left child 2 and right child 3, or it could be a linked list (e.g. 1 with right child 2, and 2 with right child 3) " o; g' ~1 [4 V8 n$ ^
- a: }% {1 l! S& }1 {* X
Runtime: O(n). Space complexity: O(log n)

static int? NextLeaf(int[] preOrderTraversal, int offset, Stack<int> stack)6 p5 A: F4 `6 `
        {! T; Z8 R* @0 U% x' J- E* c+ I
            if (offset == preOrderTraversal.Length - 1)
3 w+ e& f2 u6 y) e  X            {
4 M8 C$ `' [2 f9 V" w0 b                return offset;* @$ D: N& Y" v/ e  N& k
            }" [0 q& u6 G5 v% K
; Q4 U) v' v* D% i3 Z
            if (offset > preOrderTraversal.Length - 1). [- ]5 B1 x4 k2 z, y1 f3 L" t
            {& r' R% M/ B% e6 ^% O0 w( |
                return null;
  q$ @0 _$ z  K- ]7 }# S3 x. L            }, E' U: m5 U3 ]' s2 r( k7 I  c$ c

( b, M, `$ {7 B2 q$ _  J            var current = preOrderTraversal[offset];
" A1 ]) p7 g4 F( A  l6 A+ t; U            var next = preOrderTraversal[offset + 1];
6 [& D1 U8 g+ w1 n3 b) S% K( k+ |4 ]; T4 R
            // Next is smaller? Then it is the left sub-tree root! [) a( u  {; G' B" V, I+ x
            // Next item is bigger. Is it bigger than my ancestor?: ?/ z* v( R7 I+ d9 _+ n
            // No - then current is the parent, and the next item is the root of the right sub-tree
/ ?  y6 k/ X8 F8 A+ y7 f* U( Q: |            // Yes - then current is a leaf. Pop ancestors until you get to the common ancestor (and pop that one too). d8 |, h( c; [# N. Z$ K+ d% s
            if (current > next || stack.Count == 0 || next < stack.Peek())
) o7 Y. i$ ?* E4 m) F( ^            {) Z  [! g  @) T  V
                stack.Push(current);
3 U2 ~0 m) ~1 Y2 }1 y$ k                return NextLeaf(preOrderTraversal, offset + 1, stack);
+ R7 Z1 t! w  a7 O- A            }
7 s* F5 \3 N) q9 R4 P( }8 I6 |  u' [9 O" n) j& W: Z  B
            // The stack is empty, or the next is not bigger than the immediate ancestor. 
' Q! m' `! ?" k  C+ m            while (stack.Count > 0 && stack.Peek() < next) stack.Pop();
, u; T; M+ J. Z: O  H# }5 @            return offset;8 |6 Q' y) v! Y* b& `
        }
# ]1 x% ?7 {! K6 c  b
; U* d2 c- Z) A/ j: F9 a; V0 A# V/ w            if (preOrderTraversal1.Length == 0 || preOrderTraversal2.Length == 0)1 c5 o% |; d/ F
            {
) x1 @7 M0 i/ t& \4 k) f0 Y5 ?  g& o2 e                return;8 g9 p. \0 w  U' C3 x
            }
2 ~& @( {4 P- S! J8 f4 d3 U% Q
8 n3 @# a% v- n  P( P7 s            var iStack = new Stack<int>();
! p" V+ o9 a. u3 \1 y0 U, \8 c6 f3 d7 a            var jStack = new Stack<int>();
" q4 q8 z* p6 j* Q) Q( H, p            var i = NextLeaf(preOrderTraversal1, 0, iStack);6 h) g" E- Z$ c
            var j = NextLeaf(preOrderTraversal2, 0, jStack);
' b+ X# t! p5 u4 Q1 z$ V* Y; t. D/ V
            Console.WriteLine("Leaves: i {0}, j {1}", i, j);
6 J- c( c. _3 c% B- D            while (i.HasValue && j.HasValue && preOrderTraversal1[i.Value] == preOrderTraversal2[j.Value])
( M4 Q9 I2 [( |! Q& _7 }- |! n5 S            {& `. n3 w# u! H. x1 }. f+ @
                i = NextLeaf(preOrderTraversal1, i.Value + 1, iStack);! m/ D( ?1 G6 M
                j = NextLeaf(preOrderTraversal2, j.Value + 1, jStack);* L& l6 }! p- ]+ j# x0 B' \! ]! b" F/ k4 y
            }6 A, U. [/ f" @, h( d/ M
+ d3 H6 P; G1 Q( [
            Console.WriteLine("First mismatching leaves {0}, {1}", i, j);
# y" J; e7 ]' I        }

This can't be done for a generic tree, since there's no way to determine the leaves based on a pre-order traversal array.

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

本版积分规则

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