力扣labuladong——一刷day32

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

二叉树解题的思维模式分两类： 1、是否可以通过遍历一遍二叉树得到答案？如果可以，用一个 traverse 函数配合外部变量来实现，这叫「遍历」的思维模式。 2、是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值，这叫「分解问题」的思维模式。 无论使用哪种思维模式，你都需要思考： 如果单独抽出一个二叉树节点，它需要做什么事情？需要在什么时候（前/中/后序位置）做？其他的节点不用你操心，递归函数会帮你在所有节点上执行相同的操作。

一、力扣654. 最大二叉树

/**
 * 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 constructMaximumBinaryTree(int[] nums) {
        return fun(nums, 0, nums.length-1);
    }
    public TreeNode fun(int[] nums, int low, int high){
        if(low > high){
            return null;
        }
        int index = low;
        for(int i = low+1; i <= high; i ++){
            if(nums[i] > nums[index]){
                index = i;
            }
        }
        TreeNode cur = new TreeNode(nums[index]);
        TreeNode l = fun(nums,low,index-1);
        TreeNode r = fun(nums,index+1,high);
        cur.left = l;
        cur.right = r;
        return cur;
    }
}
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
27
28
29
30
31
32
33
34
35
36
37

二、力扣105. 从前序与中序遍历序列构造二叉树

/**
 * 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[] preorder, int[] inorder) {
        return fun(preorder, inorder, 0, preorder.length-1, 0, inorder.length-1);
    }
    public TreeNode fun(int[] preorder, int[] inorder, int preLeft,int preRight,int inPre,int inRight){
        if(preLeft > preRight || inPre > inRight){
            return null;
        }
        TreeNode root = new TreeNode(preorder[preLeft]);
        int len = 0;
        for(int i = inPre; i <= inRight; i ++){
            if(inorder[i] == preorder[preLeft]){
                len = i - inPre;
                break;
            }
        }
        root.left = fun(preorder, inorder, preLeft+1, preLeft+len, inPre, inPre+len-1);
        root.right = fun(preorder, inorder, preLeft+len+1,preRight, inPre+len+1,inRight);
        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
27
28
29
30
31
32
33
34
35
36

三、力扣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 {
    Map<Integer,Integer> invail;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        invail = new HashMap<>();
        for(int i = 0; i < inorder.length; i ++){
            invail.put(inorder[i],i);
        }
        return fun(inorder, postorder, 0, postorder.length-1,0,inorder.length-1);
    }
    public TreeNode fun(int[] inorder, int[] postorder, int postLeft, int postRight, int inLeft, int inRight){
        if(postLeft > postRight || inLeft > inRight){
            return null;
        }
        TreeNode root = new TreeNode(postorder[postRight]);
        int index = invail.get(postorder[postRight]);
        int len = index - inLeft;
        root.left = fun(inorder, postorder, postLeft, postLeft+len-1,inLeft, index-1);
        root.right = fun(inorder, postorder, postLeft+len,postRight-1,index+1,inRight);
        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
27
28
29
30
31
32
33
34
35
36

四、力扣889. 根据前序和后序遍历构造二叉树

/**
 * 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 {
    Map<Integer,Integer> invail;
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        invail = new HashMap<>();
        for(int i = 0; i < postorder.length; i ++){
            invail.put(postorder[i],i);
        }
        return fun(preorder,postorder,0,preorder.length-1,0,postorder.length-1);
    }
    public TreeNode fun(int[] preorder, int[] postorder, int preLeft, int preRight,int postLeft,int postRight){
        if(preLeft > preRight || postLeft > postRight){
            return null;
        }
        TreeNode cur = new TreeNode(preorder[preLeft]);
        if(preLeft == preRight)return cur;
        int index = invail.get(preorder[preLeft+1]);
        int len = index - postLeft+1;
        cur.left = fun(preorder, postorder, preLeft+1, preLeft+len, postLeft, index);
        cur.right = fun(preorder, postorder, preLeft+len+1,preRight,index+1,postRight-1);
        return cur;
    }
}
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
27
28
29
30
31
32
33
34
35
36
37