package com.wuli.algorithm.重建二叉树;
import java.util.Arrays;
/**
* 题目描述：
*
* 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。
* 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
* 例如输入前序遍历序列{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) {
// 数组长度为0的时候需要处理
if (pre.length == 0) {
return null;
}
int rootValue = pre[0];
// 数组长度为1的时候需要单独处理
if (pre.length == 1) {
return new TreeNode(rootValue);
}
// 首先找到root所在的位置 确定好中序左子树和右子树的范围
TreeNode root = new TreeNode(rootValue);
int rootIndex = 0;
for (int i = 0; i < in.length; i++) {
if (rootValue == in[i]) {
rootIndex = i;
break;
}
}
// 递归，假设root的左子树都已经构建完毕，那么只要将左子树按到root左右即可
// 这里注意Arrays.copyOfRange(int[],start,end)是[)的区间
root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, rootIndex + 1),
Arrays.copyOfRange(in, 0, rootIndex));
root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, rootIndex + 1, pre.length),
Arrays.copyOfRange(in, rootIndex, in.length));
return root;
}
public static void main(String[] args) {
int pre[] = {1, 2, 4, 7, 3, 5, 6, 8};
int in[] = {4, 7, 2, 1, 5, 3, 8, 6};
TreeNode treeNode = new Solution().reConstructBinaryTree(pre,in);
}
}
leetcode:重建二叉树
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 二叉树的遍历、按层打印、序列化 这三个操作是不一样的 二叉树的遍历常用递归的形式，那前序遍历来说，先访问根结点，在...
- 题目描述 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复...
- 2019 iOS面试题大全---全方面剖析面试2018 iOS面试题---算法相关1、七种常见的数组排序算法整理(...
- 我们开始介绍“二叉树和递归”。递归，是使用计算机解决问题的一种重要的思考方式。而二叉树由于其天然的递归结构，使得基...
