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
