[LeetCode] Construct Binary Tree from Inorder and Postorder Traversal

链接https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/

难度:Medium

题目:106. Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:

You may assume that duplicates do not exist in the tree.

翻译:给定树的中序遍历和后序遍历,构造二叉树。 注意:树中不存在重复项。

思路:本题与105. Construct Binary Tree from Preorder and Inorder Traversal类似。你要先知道

中序遍历:左子树,根节点,右子树

后序遍历:左子树,右子树,根节点

以如下这棵树为例:

            1
    --------|-------
    2               3
----|----       ----|----
4       5       6       7

前序遍历 1245367

中序遍历 4251637

后续遍历 4526731

我们可以发现,对于后序遍历来说,最后一个元素一定是根节点,也就是1。然后我们在中序遍历的结果里面找到1所在的位置,那么它的左半部分就是其左子树,右半部分就是其右子树。

我们将中序遍历左半部分425取出,同时发现后序遍历的结果也在相应的位置上面,只是顺序稍微不一样,也就是452。我们可以发现,后序遍历中的2就是该子树的根节点。

上面说到了左子树,对于右子树,我们取出637,同时发现后序遍历中对应的数据偏移了一格,并且顺序也不一样,为673。而3就是这颗右子树的根节点。

重复上述过程,通过后续遍历找到根节点,然后在中序遍历数据中根据根节点拆分成两个部分,同时将对应的后序遍历的数据也拆分成两个部分,重复递归,就可以得到整个二叉树了。

参考代码

Java

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) {
Map<Integer, Integer> inorderMap = new HashMap<Integer, Integer>();
for(int i=0; i<inorder.length; i++)
inorderMap.put(inorder[i],i);
return buildTree(inorder, 0, inorder.length-1, postorder, 0, postorder.length-1, inorderMap);

}

public TreeNode buildTree(int[] inorder, int iLeft, int iRight, int[] postorder, int pLeft, int pRight, Map<Integer, Integer> inorderMap){
if(iLeft>iRight || pLeft>pRight)
return null;
TreeNode cur = new TreeNode(postorder[pRight]);
//int i = 0;
//for(i=iLeft; i<=iRight; i++)
// if(postorder[pRight]==inorder[i])
// break;
int i = inorderMap.get(postorder[pRight]);
cur.left = buildTree(inorder, iLeft, i-1, postorder, pLeft, pLeft+i-iLeft-1, inorderMap);
cur.right = buildTree(inorder, i+1, iRight, postorder, pLeft+i-iLeft, pRight-1, inorderMap);
return cur;
}
}