[LeetCode] Construct Binary Tree from Preorder and Inorder Traversal

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

难度:Medium

题目:105. Construct Binary Tree from Preorder and Inorder Traversal

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

Note:

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

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

思路:首先,你应该知道

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

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

所以,我们可以从preorder中找到整棵树的根节点,即为preorder[0],由于preorderinorder是对同一棵树的遍历,我们可以知道preorder[0]inorder中一定也存在,不妨设preorder[0]==inorder[k]

由于inorder是中序遍历,所以k左边的就是根节点左子树的中序遍历、k右边的就是根节点右子树的中序遍历。

并且,我们已经知道了根节点左子树的节点数(与中序遍历长度相同),不妨设为l,我们可以知道preorder从1l+1就是根节点左子树的前序遍历,剩下的最后一部分就是根节点右子树的前序遍历。

由此,我们可以计算出左子树、右子树的前序遍历和中序遍历,从而可以用分治的思想,将规模较大的问题分解成为两个较小的问题,然后递归的进行处理,还原左子树和右子树,最后连通根节点一起组成一棵完整的树。

参考代码

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

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

cur.left = buildTree(preorder, pLeft+1, pLeft+i-iLeft, inorder, iLeft, i-1, inorderMap);
cur.right = buildTree(preorder, pLeft+i-iLeft+1, pRight, inorder, i+1, iRight, inorderMap);
return cur;
}
}