題目描述:
根據(jù)一棵樹的中序遍歷與后序遍歷構(gòu)造二叉樹苹粟。
注意:
你可以假設樹中沒有重復的元素荒勇。例如坟冲，給出
中序遍歷 inorder = [9,3,15,20,7]
后序遍歷 postorder = [9,15,7,20,3]
返回二叉樹
鏈接地址:https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
難度:中等
解題思路：
先復習了一下概念
前序遍歷：中左右
中序遍歷：左中右
后序遍歷：左右中
后序遍歷從后往前依次為中脐彩，在中序遍歷中找到對應的位置惋鹅，該位置的左邊構(gòu)成了左子樹王暗，右邊構(gòu)成了右子樹悔据，遞歸調(diào)用，直到中序遍歷上的指針相遇俗壹。
代碼：
class Solution {
int index;
public TreeNode buildTree(int[] inorder, int[] postorder) {
index = postorder.length - 1;
return fun(inorder, postorder, 0, inorder.length - 1);
}
private TreeNode fun(int[] inorder, int[] postorder, int start, int end) {
if (start > end) return null;
int val = postorder[index--];
for (int i = start; i <= end; i++) {
if (inorder[i] == val) {
TreeNode root = new TreeNode(val);
root.right = fun(inorder, postorder, i + 1, end);
root.left = fun(inorder, postorder, start, i - 1);
return root;
}
}
return null;
}
}
注意這里的root.right和root.left遞歸調(diào)用順序不能亂科汗。因為后序遍歷從右往左依次存放的是中，右中绷雏，右右中等等头滔，從右往左依次拿出了右子樹的中數(shù)。
分析：
時間復雜度O(NlogN)涎显，空間復雜度O(N)坤检，耗時34 ms。時間又有點長期吓，排名百分之七十早歇。
學習用時最短代碼：
public TreeNode buildTree(int[] inorder, int[] postorder) {
return build(inorder, postorder, 0, postorder.length - 1, postorder.length);
}
public TreeNode build(int[] inorder, int[] postorder, int inStart, int postEnd, int length) {
if (length == 0) return null;
int root = postorder[postEnd];
TreeNode treeNode = new TreeNode(root);
if (length == 1) return treeNode;
for (int i = length - 1; i >= 0; i--) {
if (root == inorder[inStart + i]) {
//注意這里的postEnd-length+i不等于i,數(shù)組長度變?yōu)樽訑?shù)組長度，i的下標已經(jīng)改變讨勤，
//i為左子樹長度箭跳，在postorder中為左子樹于右子樹的分界點
treeNode.left = build(inorder, postorder, inStart, postEnd - length + i, i);
treeNode.right = build(inorder, postorder, inStart + i + 1, postEnd - 1, length - 1 - i);
return treeNode;
}
}
return null;
}
只需要2 ms.....他的思路是在后序遍歷中找出中值，然后先找左值潭千，最后再找右值谱姓。這樣做遞歸調(diào)用里面的for循環(huán)次數(shù)少了很多。所以用時很短脊岳。
總結(jié)：
二叉樹的算法題還是比較薄弱逝段，這思路也是想了很長時間才想到T__T垛玻。繼續(xù)努力！Ｄ糖帚桩！
