day47（12.28）——leetcode面试经典150

106. 从中序与后序遍历序列构造二叉树

106. 从中序与后序遍历序列构造二叉树

我感觉我的数据结构都要忘光光了

题目：

题解：

/** * 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> map = new HashMap<>(); public int[] postorder; public TreeNode buildTree(int[] inorder, int[] postorder) { for(int i=0;i<inorder.length;i++) { map.put(inorder[i], i); } this.postorder = postorder; return recur(0,inorder.length-1,0,postorder.length-1); } public TreeNode recur(int left, int right, int l,int r) { if(left > right || l > r) { return null; } int root = postorder[r]; int i = map.get(root); TreeNode node = new TreeNode(root); node.left = recur(left, i-1, l, l+i-1-left); node.right = recur(i+1, right, l+i-left, r-1); return node; } }