105 Construct Binary Tree from Preorder and Inorder Traversal 从前序与中序遍历序列构造二叉树
2024-09-08 06:18:59
给定一棵树的前序遍历与中序遍历,依据此构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如,给出
前序遍历 = [3,9,20,15,7]
中序遍历 = [9,3,15,20,7]
返回如下的二叉树:
3
/ \
9 20
/ \
15 7
详见:https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/
Java实现:
/**
* 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[] pre, int[] in) {
if(pre==null||pre.length==0||in==null||in.length==0||pre.length!=in.length){
return null;
}
return reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
}
private TreeNode reConstructBinaryTree(int[] pre,int startPre,int endPre,int[] in,int startIn,int endIn){
if(startPre>endPre||startIn>endIn){
return null;
}
TreeNode tree=new TreeNode(pre[startPre]);
for(int i=startIn;i<=endIn;++i){
if(in[i]==pre[startPre]){
tree.left=reConstructBinaryTree(pre,startPre+1,startPre+i-startIn,in,startIn,i-1);
tree.right=reConstructBinaryTree(pre,startPre+i-startIn+1,endPre,in,i+1,endIn);
}
}
return tree;
}
}
最新文章
- centos7安装mysql5.7
- acm算法模板(3)
- leetcode Largest Rectangle in Histogram 单调栈
- 数学(错排):BZOJ 4517: [Sdoi2016]排列计数
- x64位windows上程序开发的注意事项
- Digital Square 搜索
- 认识大前端html+css+js
- 【bzoj4443 scoi2015】小凸玩矩阵
- redis3.0.5在linux上安装与配置
- 一款超人气代码格式化工具prettier
- CSAPP:第八章 异常控制流1
- 洛谷 P2515 [HAOI2010]软件安装 解题报告
- sudo 和环境变量
- MAC算法
- div浮停在页面最上或最下
- 【线程篇】stop() 和suspend()
- 转载:IE下div使用margin:0px auto不居中的原因
- 小菜鸟入门nginx
- How to input the newline in Numbers of Mac?
- c# 委托与事件的区别
热门文章
- 存储过程系列四: decode函数使用学习
- 【Codeforces】879D. Teams Formation 思维+模拟
- juery的跨域请求2
- UESTC(LCA应用:求两点之间的距离)
- Code-NFine:.NET快速开发平台 NFine.Framework Web框架
- android 怎么实现跑马灯效果
- bzoj3456
- 2.5 Hive中外部表的讲解
- Flutter实战视频-移动电商-14.首页_url_launcher一键拨打店长电话
- PHP文件操作功能函数大全