刷题笔记20——各种顺序的二叉树构造

我用了很长时间才慢慢明白，生活本就是一场西西弗斯式的旅行，只是无数盲目的因素因为纯粹的偶然在过去相互结合的产物，其意义也只有在人们让自己被非反思性的天真和幻觉陶醉时才能得到确定。也确如叔本华所说人生就像一副钟摆，在痛苦和无聊之间来回摆动。承认生活的无意义性需要莫大的勇气，但是也正因如此，个体的全部价值未被定义，无法禁锢，我们通过在每一步上都做出或此或彼的选择来塑造自身，将自己加冕为能赋予自身价值的唯一权威:也正因如此，生活的意义就在当下，就是“此在”，就是在无聊和痛苦之间来回摆荡过程中的每一个间隙。我希望在学生生涯的最后借助这种浅薄且片面的生活哲学,提醒自己时刻进行与自身针锋相对的思考并将此当作生活方式的一部分，能更加坦然地面对生命中纷至沓来的焦虑失望和痛苦，能更加投入到生活本身，像从子宫滑落到产道，再滑入一种对世界同样切近和彻底的沉浸之中。 --摘自知乎分享的毕业致谢

226. 翻转二叉树

class Solution {
    public TreeNode invertTree(TreeNode root) {
        traverse(root);
        return root; 
    }

    void traverse(TreeNode root){
        if(root==null) return;

        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        traverse(root.left);
        traverse(root.right);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

• 递归也写了一遍

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root==null) return null;
        TreeNode temp = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(temp);
        return root; 
    }
}
1
2
3
4
5
6
7
8
9

116. 填充每个节点的下一个右侧节点指针(注意一定要在循环前边先求size)

class Solution {
    public Node connect(Node root) {
        if(root==null) return null;
        Queue<Node> q = new LinkedList();
        q.offer(root);

        while(!q.isEmpty()){
            Node res = new Node();
            int sz = q.size();
            for(int i=0;i<sz;i++){
                Node temp = q.poll();
                if(i==0){
                    res = temp;
                }else{
                    res.next = temp;
                    res = res.next;
                    res.next = null;
                }

                if(temp.left!=null){
                    q.offer(temp.left);
                }
                if(temp.right!=null){
                    q.offer(temp.right);
                }
            }
        }
        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

114. 二叉树展开为链表

class Solution {
    // 注意这里是void
    public void flatten(TreeNode root) {
        if(root==null) return;
        flatten(root.left);
        flatten(root.right);

        TreeNode temp = root.right;
        TreeNode res = root.left;

        if(res==null){
            return;
        }else{
            root.right = res;
            root.left = null;
            while(res.right!=null){
                res = res.right;
            }
            res.right = temp;
        } 
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

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

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = inorder.length;
        if(n==0) return null;
        int cur = preorder[0];
        TreeNode root = new TreeNode();
        root.val = cur;

        if(n==1) return root;
        int i;
        for(i=0;i<n;i++){
            if(inorder[i]==cur){
                break;
            }
        }
        root.left = buildTree(Arrays.copyOfRange(preorder,1,i+1),Arrays.copyOfRange(inorder,0,i));
        root.right = buildTree(Arrays.copyOfRange(preorder,i+1,n),Arrays.copyOfRange(inorder,i+1,n));
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int n = inorder.length;
        if(n==0) return null;
        int cur = postorder[n-1];
        TreeNode root = new TreeNode();
        root.val = cur;

        if(n==1) return root;
        int i;
        for(i=0;i<n;i++){
            if(inorder[i]==cur){
                break;
            }
        }
        root.left = buildTree(Arrays.copyOfRange(inorder,0,i),Arrays.copyOfRange(postorder,0,i));
        root.right = buildTree(Arrays.copyOfRange(inorder,i+1,n),Arrays.copyOfRange(postorder,i,n-1));
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

654. 最大二叉树(我要服了，递归的时候吗，没用找到的maxloc一直用i)

lass Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        int len = nums.length;
        if(len==0) return null;
        int maxloc = -1;
        int maxvalue = Integer.MIN_VALUE;
        int i;
        for(i=0;i<len;i++){
            if(nums[i]>maxvalue){
                maxvalue = nums[i];
                maxloc = i;
            }
        }
        TreeNode root = new TreeNode();
        root.val = maxvalue;
        if(len==1) return root;
        root.left = constructMaximumBinaryTree(Arrays.copyOfRange(nums,0,maxloc));
        root.right = constructMaximumBinaryTree(Arrays.copyOfRange(nums,maxloc+1,len));
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

889. 根据前序和后序遍历构造二叉树

class Solution {
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        int len = preorder.length;
        if(len==0) return null;
        TreeNode root = new TreeNode(preorder[0]);
        if(len==1) return root;
        
        int l = preorder[1];
        int r = postorder[len-2];
        int pr = getIndex(preorder,r);//1
        int pl = getIndex(postorder,l);//

        if(l==r){
            root.left = constructFromPrePost(Arrays.copyOfRange(preorder,1,len),Arrays.copyOfRange(postorder,0,len-1));
            root.right = null;
            return root;
        }
        
        root.left = constructFromPrePost(Arrays.copyOfRange(preorder,1,pr),Arrays.copyOfRange(postorder,0,pl+1));
        root.right = constructFromPrePost(Arrays.copyOfRange(preorder,pr,len),Arrays.copyOfRange(postorder,pl+1,len-1));
        return root;
    }

     public static int getIndex(int[] arr, int value) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == value) {
                return i;                  //字符串时，换为 equals
            }
        }
        return -1;//如果未找到返回-1
    }
}
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