 1141主题 3486积分   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_VALUEfor 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主题 3584积分   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主题 3558积分   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).1 c8 M+ B% u\$ N; s) d% n 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). 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)) t0 Z7 J- [) A\$ a\$ g- w # B9 S" O( c2 m) E5 A Runtime: O(n). Space complexity: O(log n)``````static int? NextLeaf(int[] preOrderTraversal, int offset, Stack stack) {8 ?; i' I' @& X! _4 \. e if (offset == preOrderTraversal.Length - 1) {+ u+ W! I0 S9 Q, `& ` return offset;\$ d\$ ^" A. q) K* M } if (offset > preOrderTraversal.Length - 1) {+ W0 ~ M" |) f; `. z R& c return null; }% A: V7 o& h5 j, z0 g% z! w # ?) R2 S( c2 I+ o* y* C var current = preOrderTraversal[offset]; var next = preOrderTraversal[offset + 1]; // Next is smaller? Then it is the left sub-tree root // Next item is bigger. Is it bigger than my ancestor? // No - then current is the parent, and the next item is the root of the right sub-tree // Yes - then current is a leaf. Pop ancestors until you get to the common ancestor (and pop that one too) if (current > next || stack.Count == 0 || next < stack.Peek()) {) `5 P' } f: W5 E stack.Push(current); return NextLeaf(preOrderTraversal, offset + 1, stack); } // The stack is empty, or the next is not bigger than the immediate ancestor. ' j1 B& Q8 h3 I6 a6 ^( x) t while (stack.Count > 0 && stack.Peek() < next) stack.Pop(); return offset; } 2 H4 U6 Q; C4 ^' t( T( A if (preOrderTraversal1.Length == 0 || preOrderTraversal2.Length == 0) {. [5 H: Y% r# F3 ?7 {; r! g return; }& T+ T! F! u {# ]/ i3 o7 m& c ( t. i% H0 b& |7 z+ z0 Y3 V var iStack = new Stack(); var jStack = new Stack(); var i = NextLeaf(preOrderTraversal1, 0, iStack); var j = NextLeaf(preOrderTraversal2, 0, jStack);3 [8 p! i6 O: U Console.WriteLine("Leaves: i {0}, j {1}", i, j); while (i.HasValue && j.HasValue && preOrderTraversal1[i.Value] == preOrderTraversal2[j.Value]) {0 U3 C, W% p) \9 s' X) P. |6 R i = NextLeaf(preOrderTraversal1, i.Value + 1, iStack); j = NextLeaf(preOrderTraversal2, j.Value + 1, jStack); }) j0 @4 g3 ]; M/ \+ g. p0 |" M1 ? ; v3 A p! V. T+ b% t Console.WriteLine("First mismatching leaves {0}, {1}", i, j); }``````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.
 本版积分规则 回帖后跳转到最后一页   