做网站需要多少人,全国物流货运平台,贵州茅台酒股份有限公司网站,内蒙建设工程信息网站题目描述根据一棵树的中序遍历与后序遍历构造二叉树。注意:你可以假设树中没有重复的元素。示例#xff1a;例如#xff0c;给出中序遍历 inorder [9,3,15,20,7]后序遍历 postorder [9,15,7,20,3]返回如下的二叉树#xff1a;3/ \9 20/ \15 7思路1.思路与105. 从前序与中序…题目描述根据一棵树的中序遍历与后序遍历构造二叉树。注意:你可以假设树中没有重复的元素。示例例如给出中序遍历 inorder [9,3,15,20,7]后序遍历 postorder [9,15,7,20,3]返回如下的二叉树3/ \9 20/ \15 7思路1.思路与105. 从前序与中序遍历序列构造二叉树基本一致。2.在二叉树后序遍历的数组中找到根的位置。3.然后中序遍历的数组中根据根的值找到左子树和右子树的分割点递归下去即可。Java代码实现public TreeNode buildTree(int[] inorder, int[] postorder) {return buildTree(inorder,0,inorder.length-1,postorder,0,postorder.length-1);}public TreeNode buildTree(int[] inorder,int inStart,int inEnd, int[] postorder,int postStart,int postEnd) {if(inStart inEnd || postStart postEnd)return null;//根的值int rootVal postorder[postEnd];int i;for (i 0; i inEnd - inStart; i) {if(inorder[inStarti] rootVal)break;}TreeNode root new TreeNode(rootVal);root.left buildTree(inorder,inStart,inStarti-1,postorder,postStart,postStarti-1);root.right buildTree(inorder,inStarti1,inEnd,postorder,postStarti,postEnd-1);return root;}
