106.Construct Binary Tree from Inorder and Postorder Traversal
程序员文章站
2022-03-07 23:50:19
...
题目描述(中等难度)
思路分析
可以先看一下 105 题,直接在 105 题的基础上改了,大家也可以先根据 105 题改一改。
105 题给的是先序遍历和中序遍历,这里把先序遍历换成了后序遍历。
区别在于先序遍历的顺序是 根节点 -> 左子树 -> 右子树。
后序遍历的顺序是 左子树 -> 右子树 -> 根节点。
我们当然还是先确定根节点,然后在中序遍历中找根节点的位置,然后分出左子树和右子树。
对于之前的解法一,传数组的两个边界,影响不大,只要重新计算边界就可以了。
解法一
常规解法,利用递归,传递左子树和右子树的数组范围即可。
import java.util.HashMap;
class TreeNode{
int val;
TreeNode left;
TreeNode right;
TreeNode(int x){val=x;}
}
public class Construct_Binary_Tree_from_Inorder_and_Postorder_Traversal {
public static TreeNode buildTree(int[]inorder,int[]postorder) {
HashMap<Integer,Integer>map=new HashMap<>();
for(int i=0;i<inorder.length;i++) {
map.put(inorder[i],i);
}
return builderTreeHelper(inorder,0,inorder.length,postorder,0,postorder.length,map);
}
private static TreeNode builderTreeHelper(int[] inorder, int i_start, int i_end, int[] postorder, int p_start, int p_end,HashMap<Integer,Integer>map) {
if(p_start==p_end) return null;
int root_val=postorder[p_end-1];
TreeNode root=new TreeNode(root_val);
int i_root_index=map.get(root_val);
int leftNum=i_root_index-i_start;
root.left = builderTreeHelper(inorder, i_start, i_root_index, postorder, p_start, p_start + leftNum, map);
root.right = builderTreeHelper(inorder, i_root_index + 1, i_end, postorder, p_start + leftNum, p_end - 1,map);
return root;
}
public static void main(String args[]) {
int[] preorder= {9,3,15,20,7};
int[] inorder= {9,15,7,20,3};
TreeNode ans=buildTree(preorder,inorder);
System.out.println(ans.val);
}
}
参考文献
1.https://zhuanlan.zhihu.com/p/74277078
上一篇: vscode中的vue项目报错Property ‘xxx‘ does not exist on type ‘CombinedVueInstance<{ readyOnly...Vetur(2339)
下一篇: 浅谈Laravel中如何对大文件进行加密
推荐阅读
-
Binary Tree Postorder Traversal
-
LeetCode 105 Construct Binary Tree from Preorder and Inorder Traversal
-
LeetCode: 105. Construct Binary Tree from Preorder and Inorder Traversal
-
leetcode 随笔 Construct Binary Tree from Preorder and Inorder Traversal
-
105. Construct Binary Tree from Preorder and Inorder Traversal
-
Construct Binary Tree from Preorder and Inorder Traversal
-
Construct Binary Tree from Preorder and Inorder Traversal
-
Given a binary tree, return the postorder traversal of its nodes' values.非递归后续遍历
-
LeetCode(106)Construct Binary Tree from Inorder and Postorder Traversal
-
leetcode: binary-tree-postorder-traversal:后序遍历二叉树