**
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.
**
誰(shuí)能告訴我，為什么上面我加了 ** ，也沒(méi)能將字體加粗嗎？今天研究了下Markdown，也沒(méi)找到問(wèn)題所在。求大神指點(diǎn)啊。。。
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題目一開(kāi)始沒(méi)引起重視。還好，是medium。還算應(yīng)付的來(lái)。
先去洗個(gè)澡兒?；貋?lái)寫(xiě)。
coming back
這次題目就是給你兩個(gè) 數(shù)列，一個(gè)是inorder遍歷tree得到的數(shù)組，一個(gè)是postorder遍歷tree得到的數(shù)組。根據(jù)這兩個(gè)數(shù)列，還原出原tree。
首先，我們得明白什么是inorder, postorder。
下面是維基百科的解釋
pre-order: 中-左-右
in-order: 左-中-右
post-order: 左-右-中
現(xiàn)在假設(shè)我們有這樣的一棵樹(shù)。
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
因?yàn)閿?shù)組是int,所以用數(shù)字來(lái)代替字母。
然后我們可以發(fā)現(xiàn)，由于postorder遍歷的原理，postorder[] 的最后一位一定是頭結(jié)點(diǎn)。
于是找到了這個(gè)頭結(jié)點(diǎn)。
然后遍歷inorder[],找到這個(gè)Value對(duì)應(yīng)的Key值，這個(gè)key值就是數(shù)組里頭結(jié)點(diǎn)的index。
然后，由于inorder遍歷的特性，其左邊一定是左支樹(shù)，右邊是右支樹(shù)。于是斷成兩個(gè)sub inorder array.
同時(shí)，我們可以根據(jù)頭結(jié)點(diǎn)在inorder中的index，將postorder array同樣分裂為兩個(gè)sub postorder array.
這樣，我們就有了左支樹(shù)的inorder array and post array,也有了右支樹(shù)的。
然后就可以再次調(diào)用該函數(shù)，其實(shí)就是遞歸啦。一次遞歸下去，直到最后完成樹(shù)上所有結(jié)點(diǎn)的構(gòu)建。
兩個(gè)注意點(diǎn)：
1.一開(kāi)始傳進(jìn)來(lái)的array可能為空，需要進(jìn)行判斷。這里卡了我很久。
2.遍歷到最后，可能出現(xiàn)分出來(lái)的左支樹(shù)或者右支樹(shù)為空，會(huì)造成arrayIndexOutOfBounded Exception. 需要注意這個(gè)情況。
**
總結(jié)：
pre-order
in-order
post-order
recursion
**
之前說(shuō)的函數(shù)編程和動(dòng)態(tài)規(guī)劃很是復(fù)雜。我的能力還不足以概括，給出鏈接。
函數(shù)編程：
http://www.zhihu.com/question/28292740
動(dòng)態(tài)規(guī)劃：
http://www.zhihu.com/question/23995189
這是我覺(jué)得寫(xiě)的挺不錯(cuò)的兩個(gè)專欄。有時(shí)間在研究。
然后答應(yīng)的C來(lái)寫(xiě)面向?qū)ο蠛虲++中的模板與繼承，還正在看，火候還不夠。明后天總結(jié)。
要考試了額。。。到現(xiàn)在學(xué)校考試的題目還沒(méi)有刷。。。
Anyway, Good luck, Richardo!
為什么我之前的代碼寫(xiě)的這么復(fù)雜。。。懶得看了，貼上這次我寫(xiě)的代碼
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;
}
}
感覺(jué)思路比以前清楚多了。
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;
}
}
}
感覺(jué)就是 Binary search 的一個(gè)改編版。不難
Anyway, Good luck, Richardo! --- 08/06/2016
