126. Max Tree

1

September 2, 2016 by oneOokay

弄了好久。。。果然我的Tree的这部分烂到不行啊。感觉这个要背下来。。。

这两个用的一个解法,相对来说比九章的好理解一些:

public TreeNode maxTree(int[] A) {
if (A == null || A.length == 0) {
return null;
}
Stack<TreeNode> stack = new Stack<TreeNode>(); //这是一个递减的stack,因为只有当node.val < stack.element的时候,stack才不会pop任何值,node被push入stack。
for (int i = 0; i < A.length; i++) {
TreeNode node = new TreeNode(A[i]);//每处理一个值,往前看一位(peek)。目标是:找到左边的最大的小于node的元素x(此时为最后一个pop出来的元素,因为此stack为一个递减栈),把它当做node左叶节点。因为当node.vale >= stack.peek的时候,说明,这个node会是一个父节点,左边的所有元素都应该在他的左子树当中,而左边的最大的一个小于node的元素应该为该node的左叶节点。我们需要找到它。

//不用理pop掉比node小但不是最大的元素的原因是:两种情况:

  • 一直pop到栈为空,目前的node为最大值,该node为原来的”root”的right parent. 结束while循环,直接push node入栈。
  • 一直pop到遇到一个比node大的值:while loop找到了比它小的最大的值,找到了他的左儿子,结束while loop。进入if的时候,知道stack.peek是它的left parent。此时的stack.peek().right = node更新了之前的stack.peek()的右儿子。
    • 比如栈[4, 2,1 ,可以知道4的右儿子是2,2的右儿子是1. 当node为3结束while loop时,3的左儿子为2,(2的右儿子是1不变). 进入if的时候,把4的右儿子由2更新为3. 完成。

while (!stack.isEmpty() && node.val >= stack.peek().val) {//递减栈
node.left = stack.pop();
}

//当stack非空,说明已经找到了该node的左子叶(stack中留下的数都大于node,最新pop出去的那个是最大的比node小的数),同时这个node是目前比stack.peek这个元素的最大的一个数,所以node为stack.peek的右子叶。
if (!stack.isEmpty()) {
stack.peek().right = node;
}
stack.push(node);
}

//将剩下的node都pop出来,最后一个为整个array的最大值也就是该max tree的root,作为结果返回。

TreeNode rst = stack.pop();
while(!stack.isEmpty()) {
rst = stack.pop();
}
return rst;
}

九章解法一二:TODO

 

 

Advertisements

One thought on “126. Max Tree

  1. […] 疑惑了一下Array heapify 成一个max heap和build 一个max tree(https://oneokay.wordpress.com/2016/09/02/126-max-tree/)有什么不同: […]

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: