leetcode传送通道
/**
* 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) {
// if(postorder.length==0){
// return null;
// }
// TreeNode root = new TreeNode(postorder[postorder.length-1]);
// if(postorder.length==1){
// return root;
// }
// // 寻找切割点
// int idx;
// for(idx = 0; idx<inorder.length; idx++){
// if(inorder[idx] == root.val){
// break;
// }
// }
// // 递归子数组
// root.left = buildTree(Arrays.copyOfRange(inorder,0,idx), Arrays.copyOfRange(postorder,0,idx));
// root.right = buildTree(Arrays.copyOfRange(inorder,idx+1,inorder.length), Arrays.copyOfRange(postorder,idx,postorder.length-1));
// return root;
// }
// }
// 解法二
class Solution {
Map<Integer,Integer> map; // 转换inorder,更快查找切割点索引
public TreeNode buildTree(int[] inorder, int[] postorder) {
map = new HashMap<>();
for(int i = 0; i<inorder.length; i++){
map.put(inorder[i],i);
}
return recur(inorder, 0, inorder.length, postorder, 0, postorder.length);
}
// 参数:中序数组-处理起点-处理终点,三者确定新的中序数组,,,后序同理
private TreeNode recur(int[] inorder, int inStart, int inEnd, int[] postorder, int poStart, int poEnd){
// 终止条件
if (inStart == inEnd || poStart == poEnd) {// 相等了就到叶子了
return null;
}
// 递归逻辑
int rootVal = postorder[poEnd-1];
TreeNode root = new TreeNode(rootVal);
int rootIdx = map.get(rootVal);
root.left = recur(inorder, inStart, rootIdx, postorder, poStart, poStart+rootIdx-inStart);
root.right = recur(inorder, rootIdx+1, inEnd, postorder, poStart+rootIdx-inStart, poEnd-1);
return root;
}
}