【剑指 Offer】07.重建二叉树
2024-09-06 19:19:34
题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
示例：
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/
9 20
/
15 7
限制：
0 <= 节点个数 <= 5000
Java
public class Solution07 {
public static void main(String[] args) {
int[] preorder = {3, 9, 20, 15, 7};
int[] inorder = {9, 3, 15, 20, 7};
Solution07 s = new Solution07();
TreeNode t = s.buildTree(preorder, inorder);
System.out.println(t);
}
/**
* 方法一：递归重建
* 从前序遍历中找到根节点位置，然后得到其左右子树，最后递归重建
*/
int [] preorder;
HashMap<Integer, Integer> map = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.preorder = preorder;
for (int i = 0; i < inorder.length; ++i) {
map.put(inorder[i], i);
}
return reBuild(0, 0, inorder.length - 1);
}
public TreeNode reBuild(int root, int left, int right) {
if (left > right) {
return null;
}
TreeNode node = new TreeNode(preorder[root]); // 建立根节点
int i = map.get(preorder[root]); // 划分根节点、左右子树
node.left = reBuild(root + 1, left, i - 1);
node.right = reBuild(root + 1 + i - left, i + 1, right);
return node;
}
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
@Override
public String toString() {
return "TreeNode [" + (left != null ? "left=" + left + ", " : "")
+ (right != null ? "right=" + right + ", " : "") + "val=" + val + "]";
}
}
C++
Python
总结
最新文章
- Net设计模式实例系列文章总结
- iframe用法总结
- hihoCoder #1199 : Tower Defense Game ——（树型dp）
- FZU 2183 字符串处理
- 怎样去掉FireFox的导入向导
- sqlserver 行转列、列转行[转]
- Spark SQL概念学习系列之Spark SQL 优化策略（五）
- php ob_ 开头的相关函数
- 线关节(Line Joint)
- 基于 HTML5 Canvas 的 3D 机房创建
- assert断言
- Android源码浅析（五）——关于定制系统，如何给你的Android应用系统签名
- PHP写的爬虫，爬指定网站页面上的各种图片
- Scala并发编程【快速入门】
- CSRF与JSON
- 推荐几个Windows工具软件: HDDB - Everything的替代品
- centos 安装docker-compose
- js生成条形码插件
- C#中类的属性的获取
- UVA 624 CD(DP + 01背包)