Given an integer array with no duplicates. A max tree building on this array is defined as follow:
- The root is the maximum number in the array
- The left subtree and right subtree are the max trees of the subarray divided by the root number.
Construct the max tree by the given array.
Example
Given
[2, 5, 6, 0, 3, 1]
, the max tree constructed by this array is: 6
/ \
5 3
/ / \
2 0 1
Challenge
O(n) time and memory.
Solution:For any node x of the array, its parent must be the first number greater than it.
– ….., L, <X, …,<X, X, <X, …, <X, R,…
– 如果L<R,[L, R]里一定R先做根。然后[L, R)里L先做根,然后就是X
– 如果L>R, [L, R]里一定L先做根。然后(L, R]里R先做根,然后就是X
• 如何找到每个值左右第一个比它大的值?
– 单调递减栈
Code (Java)
/** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { /** * @param A: Given an integer array with no duplicates. * @return: The root of max tree. */ public TreeNode maxTree(int[] A) { if (A == null || A.length == 0) { return null; } Stack<TreeNode> stack = new Stack<>(); stack.push(new TreeNode(A[0])); for (int i = 1; i < A.length; i++) { TreeNode curr = new TreeNode(A[i]); while (!stack.isEmpty() && curr.val > stack.peek().val) { TreeNode top = stack.pop(); if (stack.isEmpty() || curr.val < stack.peek().val) { curr.left = top; } else { stack.peek().right = top; } } stack.push(curr); } // now the stack is a mono descreasing stack // while (stack.size() > 1) { TreeNode top = stack.pop(); stack.peek().right = top; } return stack.pop(); } }
No comments:
Post a Comment