[[左子树的前序遍历结果],[右子树的前序遍历结果],根节点]
[[左子树的前序遍历结果],根节点,[右子树的前序遍历结果]]
从后往前遍历后序遍历序列,首先拿到整棵树的根节点的值 带着该值去中序遍历序列中找到该值的定位,将中序遍历分为左右两部分 得出左右两部分的长度之后,就可以在后序遍历序列中找到左子树的根节点和右子树的根节点,重复上述步骤
比较麻烦的是区间的更新
buildMyTree(
int[] inorder 中序遍历序列
,int[] postorder 后序遍历序列
,int inorder_left 当前树在中序遍历序列的左区间
,int inorder_right 当前树在中序遍历序列的左区间
,int postorder_left 当前树在中序遍历序列的左区间
,int postorder_right 当前树在中序遍历序列的左区间
)
1. 在后序遍历序列中获得根节点的值 2. 获得根节点在中序遍历序列中的定位 3. 构建根节点 4. 递归地遍历左子树,将左子树的根节点赋给根节点的左子节点 5. 递归地遍历右子树,将右子树的根节点赋给根节点的右子节点 6. 返回根节点
class Solution { Map<Integer,Integer> map=new HashMap<>(); public TreeNode buildMyTree(int[] inorder,int[] postorder,int inorder_left,int inorder_right,int postorder_left ,int postorder_right) { if(postorder_left>postorder_right) { return null; } int post=postorder[postorder_right]; int in=map.get(post); //System.out.println(post+" "+in); int leftlen=in-1-inorder_left+1; int rightlen=inorder_right-(in+1)+1; TreeNode head=new TreeNode(post); head.left=buildMyTree(inorder,postorder,inorder_left,in-1,postorder_left,postorder_left+leftlen-1); head.right=buildMyTree(inorder,postorder,in+1,inorder_right,postorder_left+leftlen,postorder_right-1); return head; } public TreeNode buildTree(int[] inorder, int[] postorder) { int n=inorder.length; for(int i=0;i<n;i++) { map.put(inorder[i],i); } return buildMyTree(inorder,postorder,0,n-1,0,n-1); } }