重建二叉树

题目描述

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。

分析

先序遍历第一个数为根节点。找到根节点在中序遍历中的位置,可得左子树的长度,进而可分别得到左右子树的先序和中序遍历,递归。

代码:

public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
return buildTree(pre, 0, pre.length, in, 0, in.length);
}
TreeNode buildTree(int[] pre, int begin1, int end1, int[] in, int begin2, int end2) {
if (begin1 == end1) return null;
TreeNode root = new TreeNode(pre[begin1]);
int inPos = find(in, begin2, end2, pre[begin1]);
int leftSize = inPos - begin2;
root.left = buildTree(pre, begin1 + 1, begin1 + leftSize + 1, in, begin2, begin2 + leftSize);
root.right = buildTree(pre, begin1 + leftSize + 1, end1, in, inPos + 1, end2);
return root;
}
int find(int[] in, int begin2, int end2, int val) {
for (int i = begin2; i < end2; i++) {
if (in[i] == val)
return i;
}
return -1;
}
}

欢迎关注公众号: FullStackPlan 获取更多干货

Copyright © 2016 - 2017 LBD All Rights Reserved.

访客数 : | 访问量 :