四道题弄懂根据遍历顺序构造二叉树

模板：

构造二叉树:

public TreeNode f(..){
    TreeNode root=..;
    root.left=f(..);
    root.right=f(..);
    return root;
}

 根据序列构造二叉树：

Map<Integet,Integet>
public main(int[] nums){
    return f(nums,0,nums.length-1);
}
public TreeNode f(int[] nums,int left,int right){
    if(left>right)    return null;
    TreeNode root=new TreeNode(nums[index]);
    int k=map.get(index);
    root.left=f(nums,left,k-1);
    root.right=f(nums,k+1,right);
    return root;
} 

1.合并二叉树（LeetCode617）

class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null) {
            return t2;
        }
        if (t2 == null) {
            return t1;
        }
        TreeNode merged = new TreeNode(t1.val + t2.val);
        merged.left = mergeTrees(t1.left, t2.left);
        merged.right = mergeTrees(t1.right, t2.right);
        return merged;
    }
}

2.最大二叉树（LeetCode654）

模板题

class Solution {
    Map<Integer,Integer> map=new HashMap<>();
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        for(int i=0;i<nums.length;i++)  map.put(nums[i],i);
        return f(nums,0,nums.length-1);
    }
    public TreeNode f(int[] nums,int left,int right){
        if(left>right)  return null;
        int max=-1;
        for(int i=left;i<=right;i++)    max=Math.max(max,nums[i]);
        int k=map.get(max);
        TreeNode root=new TreeNode(max);
        root.left=f(nums,left,k-1);
        root.right=f(nums,k+1,right);
        return root;
    }
}

3.从前序与中序遍历构造二叉树（LeetCode105）

class Solution {
    Map<Integer,Integer> map=new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for(int i=0;i<inorder.length;i++)   map.put(inorder[i],i);
        return f(preorder,inorder,0,preorder.length-1,0,inorder.length-1);
    }
    public TreeNode f(int[] preorder,int[] inorder,int pLeft,int pRight,int inLeft,int inRight){
        if(pLeft>pRight)    return null;
        TreeNode root=new TreeNode(preorder[pLeft]);
        int k=map.get(root.val);
        root.left=f(preorder,inorder,pLeft+1,pLeft+1+k-1-inLeft,inLeft,k-1);
        root.right=f(preorder,inorder,pLeft+1+k-1-inLeft+1,pRight,k+1,inRight);

        return root;
    }
}

4.从中序和后序遍历构造二叉树（LeetCode106）

class Solution {
    Map<Integer,Integer> map=new HashMap<>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for(int i=0;i<inorder.length;i++)   map.put(inorder[i],i);
        return f(postorder,inorder,0,postorder.length-1,0,inorder.length-1);
    }
     public TreeNode f(int[] postorder,int[] inorder,int pLeft,int pRight,int inLeft,int inRight){
        if(pLeft>pRight)    return null;
        TreeNode root=new TreeNode(postorder[pRight]);
        int k=map.get(root.val);
        root.left=f(postorder,inorder,pLeft,pRight-1-inRight+k,inLeft,k-1);
        root.right=f(postorder,inorder,pRight-1-inRight+k+1,pRight-1,k+1,inRight);

        return root;
    }
}