My code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder == null || preorder.length == 0)
return null;
if (inorder == null || inorder.length == 0)
return null;
if (preorder.length != inorder.length)
return null;
return buildTree(0, preorder.length - 1, 0, inorder.length - 1, preorder, inorder);
}
private TreeNode buildTree(int preorderBegin, int preorderEnd, int inorderBegin, int inorderEnd, int[] preorder, int[] inorder) {
if (preorderEnd > preorderBegin || inorderEnd > inorderBegin)
return null;
else if (preorderBegin == preorderEnd)
return new TreeNode(preorder[preorderBegin]);
TreeNode root = new TreeNode(preorder[preorderBegin]);
int rootIndex = 0;
for (int i = inorderBegin; i <= inorderEnd; i++) {
if (inorder[i] == preorder[preorderBegin]) {
rootIndex = i;
break;
}
}
int leftTreeSize = rootIndex - inorderBegin;
root.left = buildTree(preorderBegin + 1, preorderBegin + leftTreeSize, inorderBegin, rootIndex - 1, preorder, inorder);
root.right = buildTree(preorderBegin + leftTreeSize + 1, preorderEnd, rootIndex + 1, inorderEnd, preorder, inorder);
return root;
}
}
My test result:
这道题目做了大概一个多小时,还没做出来。因为我的意识一开始出了问题,考虑错了一个东西。然后后期发现了,但是逻辑已经乱了,很难再次阻止有效的进攻了。
哪里错了呢? 两点。
preorder 的范围 [begin, end] 并不是 inorder 的范围,如果直接拿begin, end 来作为inorder[] 数组的边界条件,就会出错。所以必须要分为两个范围。
[preorderBegin, preorderEnd]
[inorderBegin, inorderEnd]
这两个范围。
第二个错误,错的更深,其实到最后都没有彻底意识到,一定要当心,做此类题时。
即,我通过preorder[begin] 到inorder[]里面找到root。
然后!
root 的右边一个数字,不一定是,就是root的右结点!
我怎么错的?
我把inorder[rootIndex + 1] 在 preorder[] 数组中找了出来,把它当做是右侧子树的begin。其实不是。可能他只是右侧子树的一个节点,而真正的头结点,他并没有包含进去。
同样。root 左侧的一个数字,不一定就是root左子树的最后一个结点,不一定是end
你可以想一下,如果,左子树是一个没有右儿子的树,那么inorder 中,root左侧的一个数字,是该左子树的左儿子。但是,在preorder中,左子树的范围结束与,即end = 左子树的结点,根据访问顺序。
所以,绝对不能简单地把root左侧的数字当做左子树end,把root右侧的数字当做右子树begin。
然后就是, preorder 与 inorder 的范围不是一致的,必须要分开传入子函数,否则一定会错。
通过 postorder 与 inorder 来重构树,也是一个道理。上次做这道题目虽然很轻松地过了,但是一定是瞎猫碰到死耗子,蒙混过关。刚刚说的那些错误点,在这个类型里面同样存在!
** 这种类型的题目,最好的解法,就是算出左侧树的size,然后把它加给 preorder + leftSize 就可以得到preorder 的end。然后 这个end +1 就可以得到右侧树的preorderBegin.**
下面在略微复习下树的遍历。
再推荐一个博客。
http://bangbingsyb.blogspot.com/2014/11/leetcode-construct-binary-tree-from.html
**
总结: 注意点已经在上面全部加粗表示了。
**
Anyway, Good luck, Richardo!
My code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder == null || preorder.length == 0)
return null;
if (inorder == null || inorder.length == 0)
return null;
return helper(0, preorder.length - 1, 0, inorder.length - 1, preorder, inorder);
}
private TreeNode helper(int p1, int p2, int i1, int i2, int[] preorder, int[] inorder) {
if (p2 <= p1) {
return new TreeNode(preorder[p1]);
}
int head = preorder[p1];
int headInorder = 0;
for (int i = i1; i <= i2; i++) {
if (inorder[i] == head) {
headInorder = i;
break;
}
}
int leftNum = headInorder - i1;
TreeNode headNode = new TreeNode(head);
if (leftNum > 0)
headNode.left = helper(p1 + 1, p1 + leftNum, i1, headInorder - 1, preorder, inorder);
if (leftNum + 1 < p2 - p1 + 1)
headNode.right = helper(p1 + leftNum + 1, p2, headInorder + 1, i2, preorder, inorder);
return headNode;
}
}
这次写还是比较顺利地。思路清晰的话,这道题木很简单。
Anyway, Good luck, Richardo!
My code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder == null || inorder == null || preorder.length != inorder.length) {
return null;
}
return helper(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
}
private TreeNode helper(int[] preorder, int[] inorder, int preLo, int preHi, int inLo, int inHi) {
if (inLo > inHi) {
return null;
}
else if (inLo == inHi) {
return new TreeNode(inorder[inLo]);
}
else {
int index = 0;
for (int i = inLo; i <= inHi; i++) {
if (inorder[i] == preorder[preLo]) {
index = i;
break;
}
}
TreeNode root = new TreeNode(preorder[preLo]);
root.left = helper(preorder, inorder, preLo + 1, preLo + index - inLo, inLo, index - 1);
root.right = helper(preorder, inorder, preLo + index - inLo + 1, preHi, index + 1, inHi);
return root;
}
}
}
想想当初刷题真的很认真。找实习的时候不该不自信的!!付出了这么多努力,就因为畏惧,都不敢投出简历!!!
最后实习找成这样,全职也受影响!不甘心!
加油。
Anyway, Good luck, Richardo! -- 08/06/2016