树构造

# 105. 从前序与中序遍历序列构造二叉树 (opens new window)

class Solution {
    int[] preorder;
    int[] inorder;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorder = inorder;
        return dfs(0,preorder.length-1,0,inorder.length-1);
    }
    TreeNode dfs(int preStart,int preEnd,int inStart,int inEnd){
        if(preStart>preEnd)
            return null;
        int rootVal = preorder[preStart];
        int anchor = 0;
        for(int i=inStart;i<=inEnd;i++){
            if(inorder[i]==rootVal){
                anchor = i;
                break;
            }
        }
        int leftSize = anchor-inStart;
        TreeNode root = new TreeNode(rootVal);
        root.left = dfs(preStart+1,preStart+leftSize,inStart,anchor-1);
        root.right = dfs(preStart+1+leftSize,preEnd,anchor+1,inEnd);
        return root;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# 106. 从中序与后序遍历序列构造二叉树 (opens new window)

# 108. 将有序数组转换为二叉搜索树 (opens new window)

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return dfs(nums,0,nums.length-1);
    }
    TreeNode dfs(int[] nums,int l,int r){
        if(r<l) return null;
        int mid = (r+l)>>>1;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = dfs(nums,l,mid-1);
        root.right = dfs(nums,mid+1,r);
        return root;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13

# 297. 二叉树的序列化与反序列化 (opens new window)

# 617. 合并二叉树 (opens new window)

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1==null) return root2;
        if(root2==null) return root1;
        TreeNode root = new TreeNode(0);
        root.val = root1.val+root2.val;
        root.left = mergeTrees(root1.left,root2.left);
        root.right = mergeTrees(root1.right,root2.right);
        return root;
    }
}

1
2
3
4
5
6
7
8
9
10
11

# 654. 最大二叉树 (opens new window)

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return dfs(nums,0,nums.length-1);
    }
    TreeNode dfs(int[] nums,int l,int r){
        if(l>r) return null;
        int max = Integer.MIN_VALUE;
        int idx = 0;
        for(int i=l;i<=r;i++){
            if(nums[i]>=max){
                max = nums[i];
                idx = i;
            }
        }
        TreeNode root = new TreeNode(max);
        root.left = dfs(nums,l,idx-1);
        root.right = dfs(nums,idx+1,r);
        return root;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

← 层序遍历前缀树→