106. 从中序与后序遍历序列构造二叉树
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如,给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树:
运行结果
解题思路
后序遍历最后一个节点为根节点---构造根节点
然后在中序遍历中找到根节点的位置,根据节点数确定出左右子树的中序和后序遍历数组,进行递归
java代码
/** * Definition for a binary tree node. * 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; * } * } */ class Solution { public TreeNode buildTree(int[] inorder, int[] postorder) { return build(inorder,0,inorder.length-1,postorder,0,postorder.length-1); } public TreeNode build(int[] inorder,int inStart,int inEnd,int[] postorder,int postStart,int postEnd){ if(inStart > inEnd) return null; int rootvalue=postorder[postEnd]; int index=-1; for(int i=inStart;i<=inEnd;i++){ if(inorder[i]==rootvalue){ index=i; break; } } int leftSize=index-inStart; TreeNode root=new TreeNode(rootvalue); root.left=build(inorder, inStart, index-1, postorder, postStart, postStart+leftSize-1); root.right=build(inorder,index+1,inEnd,postorder,postStart+leftSize,postEnd-1); return root; } }