05 August 2008
Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
For example, given
1
2
inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]
Return the following binary tree:
1
2
3
4
5
3
/ \
9 20
/ \
15 7
这道题是根据中序和后序来重建二叉树，依然是用递归来做， 后序的顺序的最后一个肯定是根，所以原二叉树的根节点可以知道，题目中给了一个很关键的条件就是树中没有相同元素，有了这个条件就可以在中序遍历中也定位出根节点的位置，并以根节点的位置将中序遍历拆分为左右两个部分，分别对其递归调用原函数。整个过程如下：
同样根据中序遍历找到根节点的位置，然后顺势计算出左子树串的长度。在后序遍历中分割出左子树串和右子树串，递归的建立左子树和右子树。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
return buildTree(inorder, 0, inorder.length-1, postorder, 0, postorder.length - 1);
}
private TreeNode buildTree(int[] in, int inStart, int inEnd, int[] post, int postStart, int postEnd) {
if (inStart > inEnd || postStart > postEnd) {
return null;
}
int rootVal = post[postEnd];
int rootIndex = 0;
for (int i = 0; i <= inEnd; i++) {
if (in[i] == rootVal) {
rootIndex = i;
break;
}
}
int len = rootIndex - inStart;
TreeNode root = new TreeNode(rootVal);
root.left = buildTree(in, inStart, rootIndex - 1, post, postStart, postStart + len- 1);
root.right = buildTree(in, rootIndex + 1, inEnd, post, postStart + len, postEnd - 1);
return root;
}
}
Hash表(掌握)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
HashMap<Integer, Integer> map;
public TreeNode buildTree(int[] inorder, int[] postorder) {
if (postorder == null || postorder.length == 0 || inorder == null || inorder.length == 0 || postorder.length != inorder.length) {
return null;
}
map = new HashMap<Integer, Integer>();
// 注意没有重复值，所以可以用中序的元素当作key
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
return buildTree(postorder, 0, postorder.length - 1, inorder, 0, inorder.length - 1);
}
private TreeNode buildTree (int[] postorder, int pLeft, int pRight, int[] inorder, int iLeft, int iRight) {
if (pLeft > pRight || iLeft > iRight) { // 基线条件避免死循环
return null;
}
// 1.根据后序当前的"右"边结点是root的特性重建根结点
int value = postorder[pRight];
TreeNode current = new TreeNode(value);
// 2.在中序中寻找重建的根结点的值
int index = map.get(value);
// 3.根据在中序中找到的root的左边是左子树，root的右边是右子树的特性，递归重建左右子树
int leftCount = index - iLeft;
// 左子树，前序的左边不算root，到index处；中序的左边一直到找到的root（不含）处
current.left = buildTree(postorder, pLeft, pLeft + leftCount - 1, inorder, iLeft, index - 1);
// 右子树，从index到最右边
current.right = buildTree(postorder, pLeft + leftCount, pRight - 1, inorder, index + 1, iRight);
return current;
}
}