Day 44

題目描述

思路

這題類似與昨天那題，首先來復習一下，后序遍歷，對于后序遍歷每一個元素都滿足以下規律：
（左子樹）（右子樹）（根），那么我們直接修改昨天的代碼即可。前序是從前向后找根，后序我們就從后向前找根。
代碼如下：

/*** 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 Map<Integer,Integer>indexmap;public TreeNode findroot(int[]inorder,int[]postorder,int inleft,int inright,int postleft,int postright){if(postleft>postright){return null;}int root_num=postorder[postright];//從后向前找根int in=indexmap.get(postorder[postright]);//獲取根在中序遍歷中的序號TreeNode root=new TreeNode(root_num);root.left=findroot(inorder,postorder,inleft,in-1,postleft,postright-inright+in-1);root.right=findroot(inorder,postorder,in+1,inright,postright-inright+in,postright-1);return root;}public TreeNode buildTree(int[] inorder, int[] postorder) {indexmap=new HashMap<Integer,Integer>();int n=inorder.length;for(int i=0;i<n;i++){//存放每個元素在中序遍歷中的序號indexmap.put(inorder[i],i);}TreeNode root=findroot(inorder,postorder,0,n-1,0,n-1);return root;}
}