题目描述
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
题目分析
前序遍历:中、左、右,前序遍历的第一个元素就是二叉树的根结点。
中序遍历:左、中、右,根结点的左子树都在序列的左边,右子树都在序列的右边。
基本思路:
1. 在中序遍历序列中找到根结点的位置。
2. 中序遍历序列vin
中,根结点左边的都在左子树上,右边的都在右子树上。由此可以得到left_vin
和right_vin
。
3. 遍历前序遍历序列pre
,如果元素在left_vin
中,说明在左子树上,将其添加到left_pre
;反之则将其添加到right_pre
中。
4. 现在已经分别得到左右子树的前序遍历和中序遍历序列了,递归调用此过程即可。让当前结点的左孩子指向左子树的reConstructBinaryTree
的结果,右孩子指向右子树的reConstructBinaryTree
的结果。
C++
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution
{
public:
TreeNode *reConstructBinaryTree(vector<int> pre, vector<int> vin)
{
TreeNode *res = new TreeNode(pre[0]);
vector<int> left_pre, left_vin, right_pre, right_vin;
//找到根结点在中序遍历中的位置
int root = find(vin.begin(), vin.end(), pre[0]) - vin.begin();
//找出左子树
for (int i = 0; i < root; i++)
left_vin.push_back(vin[i]);
//找出右子树
for (int i = root + 1; i < vin.size(); i++)
right_vin.push_back(vin[i]);
for (int i = 1; i < pre.size(); i++)
{
//在左子树中
if (find(left_vin.begin(), left_vin.end(), pre[i]) != left_vin.end())
left_pre.push_back(pre[i]);
else
right_pre.push_back(pre[i]);
}
//递归
if (left_vin.size() > 0)
res->left = reConstructBinaryTree(left_pre, left_vin);
if (right_vin.size() > 0)
res->right = reConstructBinaryTree(right_pre, right_vin);
return res;
}
};
Java
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
import java.util.*;
import java.util.stream.Collectors;
public class Solution {
public TreeNode reConstructBinaryTree(int[] pre2, int[] vin2) {
List<Integer> pre = Arrays.stream(pre2).boxed().collect(Collectors.toList());
List<Integer> vin = Arrays.stream(vin2).boxed().collect(Collectors.toList());
List<Integer> left_pre = new ArrayList<>(), left_vin, right_pre = new ArrayList<>(), right_vin;
TreeNode res = new TreeNode(pre2[0]);
// 找到根结点在中序遍历中的位置
int root = vin.indexOf(pre2[0]);
// 找出左子树
left_vin = vin.subList(0, root);
// 找出右子树
right_vin = vin.subList(root + 1, vin.size());
for (int x : pre.subList(1, pre.size())) {
// 在左子树中
if (left_vin.indexOf(x) != -1)
left_pre.add(x);
else
right_pre.add(x);
}
// 递归
if (left_vin.size() > 0)
res.left = reConstructBinaryTree(left_pre.stream().mapToInt(Integer::valueOf).toArray(),
left_vin.stream().mapToInt(Integer::valueOf).toArray());
if (right_vin.size() > 0)
res.right = reConstructBinaryTree(right_pre.stream().mapToInt(Integer::valueOf).toArray(),
right_vin.stream().mapToInt(Integer::valueOf).toArray());
return res;
}
}