Related: LeetCode 654 - Maximum Binary Tree
Lintcode-Max Tree - LiBlog - 博客园
Given an integer array with no duplicates. A max tree building on this array is defined as follow:
(1) 如果新来一个数,比堆栈顶的树根的数小,则把这个数作为一个单独的节点压入堆栈。
(2) 否则,不断从堆栈里弹出树,新弹出的树以旧弹出的树为右子树,连接起来,直到目前堆栈顶的树根的数大于新来的数。然后,弹出的那些数,已经形成了一个新的树,这个树作为新节点的左子树,把这个新树压入堆栈。
这样的堆栈是单调的,越靠近堆栈顶的数越小。
最后还要按照(2)的方法,把所有树弹出来,每个旧树作为新树的右子树
https://codesolutiony.wordpress.com/2015/01/28/lintcode-max-tree/
https://www.jianshu.com/p/e05e598c8073
X. Recursive
https://segmentfault.com/a/1190000007471356
https://richdalgo.wordpress.com/2015/01/28/lintcode-max-tree/
http://dinnerwanzi.blogspot.com/2015/07/lintcode-94-binary-tree-max-sum.html
Lintcode-Max Tree - LiBlog - 博客园
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.
其实这种树叫做笛卡树( Cartesian tree)。直接递归建树的话复杂度最差会退化到O(n^2)。经典建树方法,用到的是单调堆栈。我们堆栈里存放的树,只有左子树,没有有子树,且根节点最大。
Given
[2, 5, 6, 0, 3, 1]
, the max tree constructed by this array is:
6
/ \
5 3
/ / \
2 0 1
还是用到了ordered stack。对于每个数,他的左右右节点是在他与第一个比他大的数之间,比他小的最大数,因此维护一个递减stack就可以得到。
下降stack,因为遇到上升的就自动组成一个左subtree。这个stack的思想要体会。
https://segmentfault.com/a/1190000007471356
https://segmentfault.com/a/1190000007471356
public TreeNode maxTree(int[] A) {
if (A == null || A.length == 0) return null;
Stack<TreeNode> stack = new Stack<>();
for (int i = 0; i < A.length; i++) {
//遍历A的每个元素,创造结点node
TreeNode node = new TreeNode(A[i]);
//将stack中小于当前结点的结点都pop出来,存为当前结点的左子树
while (!stack.isEmpty() && node.val >= stack.peek().val) node.left = stack.pop();
//如果stack仍非空,剩下的结点一定大于当前结点,所以将当前结点存为stack中结点的右子树;而stack中结点本来的右子树之前已经存为当前结点的左子树了
if (!stack.isEmpty()) stack.peek().right = node;
//stack中存放结点的顺序为:底部为完整的max tree,从下向上是下一层孩子结点的备份,顶部是当前结点的备份
stack.push(node);
}
TreeNode root = stack.pop();
while (!stack.isEmpty()) root = stack.pop();
return root;
}
http://blog.welkinlan.com/2015/06/29/max-tree-lintcode-java/
public TreeNode maxTree(int[] A) {
// write your code here
if (A == null || A.length == 0) {
return null;
}
LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
for (int i = 0; i < A.length; i++) {
TreeNode cur = new TreeNode(A[i]);
while (!stack.isEmpty() && cur.val > stack.peek().val) {
cur.left = stack.pop();
}
if (!stack.isEmpty()) {
stack.peek().right = cur;
}
stack.push(cur);
}
TreeNode result = new TreeNode(0);
while (!stack.isEmpty()) {
result = stack.pop();
}
return result;
}
(1) 如果新来一个数,比堆栈顶的树根的数小,则把这个数作为一个单独的节点压入堆栈。
(2) 否则,不断从堆栈里弹出树,新弹出的树以旧弹出的树为右子树,连接起来,直到目前堆栈顶的树根的数大于新来的数。然后,弹出的那些数,已经形成了一个新的树,这个树作为新节点的左子树,把这个新树压入堆栈。
这样的堆栈是单调的,越靠近堆栈顶的数越小。
最后还要按照(2)的方法,把所有树弹出来,每个旧树作为新树的右子树
17 public TreeNode maxTree(int[] A) { 18 if (A.length==0) return null; 19 20 Stack<TreeNode> nodeStack = new Stack<TreeNode>(); 21 nodeStack.push(new TreeNode(A[0])); 22 for (int i=1;i<A.length;i++) 23 if (A[i]<=nodeStack.peek().val){ 24 TreeNode node = new TreeNode(A[i]); 25 nodeStack.push(node); 26 } else { 27 TreeNode n1 = nodeStack.pop(); 28 while (!nodeStack.isEmpty() && nodeStack.peek().val < A[i]){ 29 TreeNode n2 = nodeStack.pop(); 30 n2.right = n1; 31 n1 = n2; 32 } 33 TreeNode node = new TreeNode(A[i]); 34 node.left = n1; 35 nodeStack.push(node); 36 } 37 38 39 TreeNode root = nodeStack.pop(); 40 while (!nodeStack.isEmpty()){ 41 nodeStack.peek().right = root; 42 root = nodeStack.pop(); 43 } 44 45 return root; 51 }
public TreeNode maxTree(int[] A) {
Stack<TreeNode> stack = new Stack<TreeNode>();//decreasing stack
for (int i = 0; i < A.length; i++) {
TreeNode newNode = new TreeNode(A[i]);
TreeNode pre = null;
while (!stack.isEmpty() && stack.peek().val < A[i]) {
TreeNode cur = stack.pop();
if (pre != null) {
cur.right = pre;
}
pre = cur;
newNode.left = pre;
}
stack.push(newNode);
}
TreeNode preNode = null;
while (!stack.isEmpty()) {
TreeNode curNode = stack.pop();
curNode.right = preNode;
preNode = curNode;
}
return preNode;
}
- 通过观察发现规律,对于每个node的父亲节点 = min(左边第一个比它大的,右边第一个比它大的)
- 维护一个降序数组,可以实现对这个min的快速查找
# stack = [2], push 5 因为 5 > 2, 所以2是5的左儿子, pop 2
# stack = [], push 5
# stack = [5], push 6, 因为 6 > 5,所以5是6的左儿子, pop 5
# stack = [], push 6
# stack = [6], push 0, 因为0 < 6, stack = [6], 所以0是6的右儿子
# stack = [6, 0], push 3, 因为3 > 0, 所以0是3的左儿子, pop 0
# stack = [6], 所以3是6的右儿子, push 3
# stack = [6, 3], push 1, 因为1 < 3,所以1是3的右儿子
def maxTree(self, A):
# write your code here
stack = []
for element in A:
node = TreeNode(element)
while len(stack) != 0 and element > stack[-1].val:
node.left = stack.pop()
if len(stack) != 0:
stack[-1].right = node
stack.append(node)
return stack[0]
X. Recursive
https://segmentfault.com/a/1190000007471356
public TreeNode maxTree(int[] A) {
if (A == null || A.length == 0) return null;
return buildMax(A, 0, A.length-1);
}
public TreeNode buildMax(int[] A, int start, int end) {
if (start > end) return null;
int max = Integer.MIN_VALUE;
int maxIndex = -1;
for (int i = start; i <= end; i++) {
if (A[i] >= max) {
max = A[i];
maxIndex = i;
}
}
TreeNode root = new TreeNode(max);
root.left = buildMax(A, start, maxIndex-1);
root.right = buildMax(A, maxIndex+1, end);
return root;
}
https://www.cnblogs.com/lishiblog/p/4187936.html17 public TreeNode maxTree(int[] A) { 18 if (A.length==0) return null; 19 20 TreeNode root = new TreeNode(A[0]); 21 for (int i=1;i<A.length;i++) 22 if (A[i]>root.val){ 23 TreeNode node = new TreeNode(A[i]); 24 node.left = root; 25 root = node; 26 } else insertNode(root,null,A[i]); 27 28 return root; 29 } 30 31 public void insertNode(TreeNode cur, TreeNode pre, int val){ 32 if (cur==null){ 33 TreeNode node = new TreeNode(val); 34 pre.right = node; 35 return; 36 } 37 38 if (cur.val<val){ 39 TreeNode node = new TreeNode(val); 40 pre.right = node; 41 node.left = cur; 42 return; 43 } else 44 insertNode(cur.right,cur,val); 45 }
https://richdalgo.wordpress.com/2015/01/28/lintcode-max-tree/
http://dinnerwanzi.blogspot.com/2015/07/lintcode-94-binary-tree-max-sum.html
int maxPathSum(TreeNode *root) { // write your code here if (!root) return 0; myMax=INT_MIN; maxHelper(root); return myMax; } int maxHelper(TreeNode* root){ if (!root) return 0; int l=max(0, maxHelper(root->left)); int r=max(0, maxHelper(root->right)); myMax=max(myMax, l+r+root->val); return max(l,r)+root->val; } int myMax;Read full article from Lintcode-Max Tree - LiBlog - 博客园