**
Question:
Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
**
谁能告诉我，为什么上面我加了 ** ，也没能将字体加粗吗？今天研究了下Markdown，也没找到问题所在。求大神指点啊。。。
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[] inorder, int[] postorder) {
if (inorder.length == 0)
return null;
int headKey = postorder[postorder.length - 1];
TreeNode node = this.formBiTree(inorder, postorder, headKey);
return node;
}
private TreeNode formBiTree(int[] inorder, int[] postorder, int headKey) {
if (inorder.length == 1) {
TreeNode leafNode = new TreeNode(headKey);
leafNode.left = null;
leafNode.right = null;
return leafNode;
}
boolean isLeftEmpty = false;
boolean isRightEmpty = false;
int headValue = headKey;
int sentinel = 0;
for (int i = 0; i < inorder.length; i++) {
if (headValue == inorder[i]) {
sentinel = i;
break;
}
}
/* get the key of both left and right */
int leftKey = 0;
int rightKey = 0;
if (sentinel == 0)
isLeftEmpty = true;
else
leftKey = postorder[sentinel - 1];
if (sentinel == inorder.length - 1)
isRightEmpty = true;
else
rightKey = postorder[postorder.length - 2];
/* get the inorder and postorder of both left and right */
TreeNode head = new TreeNode(headValue);
int[] leftInorder;
int[] leftPostorder;
if (!isLeftEmpty) {
leftInorder = new int[sentinel];
for (int i = 0; i < leftInorder.length; i++)
leftInorder[i] = inorder[i];
leftPostorder = new int[sentinel];
for (int i = 0; i < leftPostorder.length; i++)
leftPostorder[i] = postorder[i];
head.left = formBiTree(leftInorder, leftPostorder, leftKey);
}
else
head.left = null;
int[] rightInorder;
int[] rightPostorder;
if (!isRightEmpty) {
rightInorder = new int[inorder.length - sentinel - 1];
for (int i = 0; i < rightInorder.length; i++)
rightInorder[i] = inorder[i + sentinel + 1];
rightPostorder = new int[inorder.length - sentinel - 1];
for (int i = 0; i < rightPostorder.length; i++)
rightPostorder[i] = postorder[i + sentinel];
head.right = formBiTree(rightInorder, rightPostorder, rightKey);
}
else
head.right = null;
return head;
}
public static void main(String[] args) {
Solution test = new Solution();
int[] a = {4, 2, 7, 5, 8, 1, 3, 9, 6};
int[] b = {4, 7, 8, 5, 2, 9, 6, 3, 1};
System.out.println(test.buildTree(a, b).val);
}
}
My test result:
这次的难度提前查了下，害怕又像昨天一样，碰到了一道hard题目一开始没引起重视。还好，是medium。还算应付的来。
先去洗个澡儿。回来写。
coming back
这次题目就是给你两个 数列，一个是inorder遍历tree得到的数组，一个是postorder遍历tree得到的数组。根据这两个数列，还原出原tree。
首先，我们得明白什么是inorder, postorder。
下面是维基百科的解释
pre-order: 中-左-右
in-order: 左-中-右
post-order: 左-右-中
现在假设我们有这样的一棵树。
inorder:
A B C D E F G H I
4 2 7 5 8 1 3 9 6
postorder:
A C E D B H I G F
4 7 8 5 2 9 6 3 1
因为数组是int,所以用数字来代替字母。
然后我们可以发现，由于postorder遍历的原理，postorder[] 的最后一位一定是头结点。
于是找到了这个头结点。
然后遍历inorder[],找到这个Value对应的Key值，这个key值就是数组里头结点的index。
然后，由于inorder遍历的特性，其左边一定是左支树，右边是右支树。于是断成两个sub inorder array.
同时，我们可以根据头结点在inorder中的index，将postorder array同样分裂为两个sub postorder array.
这样，我们就有了左支树的inorder array and post array,也有了右支树的。
然后就可以再次调用该函数，其实就是递归啦。一次递归下去，直到最后完成树上所有结点的构建。
两个注意点：
1.一开始传进来的array可能为空，需要进行判断。这里卡了我很久。
2.遍历到最后，可能出现分出来的左支树或者右支树为空，会造成arrayIndexOutOfBounded Exception. 需要注意这个情况。
**
总结：
pre-order
in-order
post-order
recursion
**
之前说的函数编程和动态规划很是复杂。我的能力还不足以概括，给出链接。
函数编程：
http://www.zhihu.com/question/28292740
动态规划：
http://www.zhihu.com/question/23995189
这是我觉得写的挺不错的两个专栏。有时间在研究。
然后答应的C来写面向对象和C++中的模板与继承，还正在看，火候还不够。明后天总结。
要考试了额。。。到现在学校考试的题目还没有刷。。。
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[] inorder, int[] postorder) {
if (inorder == null || inorder.length == 0)
return null;
if (postorder == null || postorder.length == 0)
return null;
return helper(0, postorder.length - 1, 0, inorder.length - 1, postorder, inorder);
}
private TreeNode helper(int p1, int p2, int i1, int i2, int[] postorder, int[] inorder) {
if (p2 <= p1) {
return new TreeNode(postorder[p1]);
}
int head = postorder[p2];
int headInorder = 0;
for (int i = i1; i <= i2; i++) {
if (inorder[i] == head) {
headInorder = i;
break;
}
}
TreeNode headNode = new TreeNode(head);
int leftNum = headInorder - i1;
if (leftNum > 0) {
headNode.left = helper(p1, p1 + leftNum - 1, i1, i1 + leftNum - 1, postorder, inorder);
}
if (leftNum + 1 < p2 - p1 + 1) {
headNode.right = helper(p1 + leftNum, p2 - 1, headInorder + 1, i2, postorder, 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[] inorder, int[] postorder) {
if (inorder == null || postorder == null || inorder.length != postorder.length) {
return null;
}
return helper(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1);
}
private TreeNode helper(int[] inorder, int[] postorder, int inLo, int inHi, int postLo, int postHi) {
if (inLo > inHi) {
return null;
}
else if (inLo == inHi) {
return new TreeNode(inorder[inLo]);
}
else {
TreeNode root = new TreeNode(postorder[postHi]);
int index = 0;
for (int i = inLo; i <= inHi; i++) {
if (inorder[i] == postorder[postHi]) {
index = i;
break;
}
}
root.left = helper(inorder, postorder, inLo, index - 1, postLo, postLo + index - inLo - 1);
root.right = helper(inorder, postorder, index + 1, inHi, postLo + index - inLo, postHi - 1);
return root;
}
}
}
感觉就是 Binary search 的一个改编版。不难
Anyway, Good luck, Richardo! --- 08/06/2016
