题目 【LeetCode|LeetCode-105-从前序与中序遍历序列构造二叉树】
文章图片
思路
- 感觉要用到递归之类的方法，因为可以通过前序遍历的数组确定根节点，那么中序找到这个根节点后，其左边的为左子树，右边的为右子树，可以通过递归构建。
- 写了个很丑陋的递归…就这样吧
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
//两个哈希表存储<值，位置>
HashMap PreMap = new HashMap<>();
HashMap inMap = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
for(int i=0;
i=1) node.left = DFS(preorder,inorder,0,local-1);
if(local+1<=preorder.length-1) node.right = DFS(preorder,inorder,local+1,preorder.length-1);
return node;
}
public TreeNode DFS(int[] preorder,int[] inorder,int start,int end){
//给出中序遍历的start和end 将其接起来
if(start==end){
TreeNode node = new TreeNode(inorder[start]);
return node;
}
//否则找到inorder[start,end]在preorder出现位置最靠前的作为根节点
int minlocal = PreMap.get(inorder[start]);
int minvalue = https://www.it610.com/article/inorder[start];
for(int i=start;
i<=end;
i++){
int nowlocal = PreMap.get(inorder[i]);
int nowvalue = inorder[i];
if(nowlocal 推荐阅读
- 一起刷好题|用好java中的String类，这些OJ题你还怕吗（）
- 一起刷好题|《二叉树刷题计划》——平衡二叉树
- 動態規劃|1130. Minimum Cost Tree From Leaf Values(DP)
- 动态规划|115、完全背包-LeetCode-139.单词拆分
- python编程笔记|链表与列表的区别
- LeetCode 825. Friends Of Appropriate Ages
- LeetCode 5126. 有序数组中出现次数超过25%的元素 Element Appearing More Than 25% In Sorted Array
- leetcode1287. Element Appearing More Than 25% In Sorted Array
- Leetcode 1031 Maximum Sum of Two Non-Overlapping Subarrays (滑动窗口)