中低端网站建设客户网,wordpress 导出 主题,大学生网站制作作业免费下载,台州网站制作开发根据一棵树的中序遍历与后序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
例如#xff0c;给出
中序遍历 inorder [9,3,15,20,7] 后序遍历 postorder [9,15,7,20,3] 返回如下的二叉树#xff1a; 3 / \ 9 20 / \ 15 7
思路#xff1a;和前…根据一棵树的中序遍历与后序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
例如给出
中序遍历 inorder [9,3,15,20,7] 后序遍历 postorder [9,15,7,20,3] 返回如下的二叉树 3 / \ 9 20 / \ 15 7
思路和前序中序构建二叉树思路一样。
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }*/
class Solution {HashMapInteger,Integer memo new HashMap();int[] post;public TreeNode buildTree(int[] inorder, int[] postorder) {for(int i 0;i inorder.length; i) memo.put(inorder[i], i);post postorder;TreeNode root buildTree(0, inorder.length - 1, 0, post.length - 1);return root;}public TreeNode buildTree(int is, int ie, int ps, int pe) {if(ie is || pe ps) return null;int root post[pe];int ri memo.get(root);TreeNode node new TreeNode(root);node.left buildTree(is, ri - 1, ps, ps ri - is - 1);node.right buildTree(ri 1, ie, ps ri - is, pe - 1);return node;}
}
