7.9号刷题

发表于 | 分类于 | 0 comments

第一题 96. Unique Binary Search Trees

题目描述

给定n，找出1, 2…n能组成的所有的Binary Search Tree的个数

算法

利用动态规划，记住每一个位置能够组成的二叉树的数量，进行不断叠加，最后得出答案

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = dp[1] = 1;
        
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                dp[i] += dp[j] * dp[i - j - 1];
            }
        }
        return dp[n];
    }
}

第二题 Unique Binary Search Trees II

题目描述

同前面题目一样，只不过现在需要找出所有的不同的子树

算法

对于中间的节点i，采用分治法。左边所有的可能是(start, i-1)右边为(i+1, end)每次切成更小的部分，然后进行树的创建

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
public class generateTrees95 {
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) return new ArrayList<>();
        return backtrack(1, n);
    }
    public List<TreeNode> backtrack(int start, int end) {
        List<TreeNode> res = new ArrayList<>();
        if (start > end) {
            res.add(null);
            return res;
        }
        if (start == end) {
            TreeNode cur = new TreeNode(start);
            res.add(cur);
            return res;
        }
        for (int i = start; i <= end; i++) {
            List<TreeNode> leftpart = backtrack(start, i - 1);
            List<TreeNode> rightpart = backtrack(i + 1, end);
            for (TreeNode leftNode : leftpart) {
                for (TreeNode rightNode : rightpart) {
                    TreeNode root = new TreeNode(i);
                    root.left = leftNode;
                    root.right = rightNode;
                    res.add(root);
                }
            }
        }
        return res;
    }
}

第三题 298. Binary Tree Longest Consecutive Sequence

题目描述

求一个二叉树中，最长的连续子树的长度。连续子树的长度定义为每次值的大小递增1

算法

每次检查当前的值是否满足上一个值加1，如果满足，递增count。并计算是否为最大值。直到遍历完整棵树为止

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class longestConsecutive298 {
    int max = 0;
    public int longestConsecutive(TreeNode root) {
        if (root == null) return 0;
        helper(root, 0, root.val);
        return max;
    }
    public void helper(TreeNode root, int count, int num) {
        if (root == null) return;
        if (root.val == num) count++;
        else count = 1;
        max = Math.max(count, max);
        helper(root.left, count, root.val + 1);
        helper(root.right, count, root.val + 1);
    }
}

第四题 549. Binary Tree Longest Consecutive Sequence II

题目描述

给定二叉树，寻找其中最长的连续的整数路径。

特别的，路径可以递增/递减。例如[1,2,3,4] 和 [4,3,2,1]均有效，但是 [1,2,4,3] 无效。另外，路径的顺序不一定必须是父亲-孩子，也可以是孩子-父亲-孩子。

算法

如果想要一遍遍历就完成整个计算，我们需要知道每一个点，对于这个点左右分别有多少个降序序列和多少个升序序列，这样就能算出对于这个点，所能形成的最大长度是多少。因此，我们对于每一个点返回一个数组，分别记录了对于这个点，左右的升降序的最大长度，然后不断更新最大长度。最后返回

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
public class longestConsecutive549 {
    int max = 0;
    public int longestConsecutive(TreeNode root) {
        if (root == null) return 0;
        helper(root);
        return max;
    }
    public int[] helper(TreeNode root) {
        if (root == null) return null;
        int as = 1, de = 1;
        if (root.left != null) {
            int[] l = helper(root.left);
            if (root.val == root.left.val + 1)
                de = l[1] + 1;
            if (root.val == root.left.val - 1)
                as = l[0] + 1;
        }
        if (root.right != null) {
            int[] r = helper(root.right);
            if (root.val == root.right.val + 1)
                de = Math.max(de, r[1] + 1);
            if (root.val == root.right.val - 1)
                as = Math.max(as, r[0] + 1);
        }
        max = Math.max(max, de + as - 1);
        return new int[]{as, de};
    }
}

第五题 199. Binary Tree Right Side View

题目描述

给定一棵二叉树，假设你站在它的右侧，自顶向下地返回你可以观察到的节点的值。

例如，给定上面的二叉树，你应该返回[1, 3, 4]。

算法

BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class rightSideView199 {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size(), num = 0;
            for (int i = 0; i < size; i++) {
               TreeNode cur = queue.poll();
               if (cur.left != null) queue.add(cur.left);
               if (cur.right != null) queue.add(cur.right);
               num = cur.val;
            }
            res.add(num);
        }
        return res;
    }
}
DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        helper(root, 0, res);
        return res;
    }
    public void helper(TreeNode root, int depth, List<Integer> res) {
        if (root == null) return;
        
        if (depth == res.size()) {
            res.add(root.val);
        }
        helper(root.right, depth + 1, res);
        helper(root.left, depth + 1, res);
    }
}

第六题 116. Populating Next Right Pointers in Each Node

题目描述

给定一个完全平衡的二叉树，将所有的左边的节点指向其右边的节点。如果右边没有节点，则指向Null

算法

BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class connect116 {
    public void connect(TreeLinkNode root) {
        if (root == null) return;
        Queue<TreeLinkNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            TreeLinkNode cur = queue.poll();
            if (cur.left != null) queue.offer(cur.left);
            if (cur.right != null) queue.offer(cur.right);
            for (int i = 0; i < size - 1; i++) {
                TreeLinkNode next = queue.poll();
                cur.next = next;
                cur = next;
                if (cur.left != null) queue.offer(cur.left);
                if (cur.right != null) queue.offer(cur.right);
            }
            cur.next = null;
        }
    }
}
DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null) return;
        
        TreeLinkNode layer = root;
        while (layer != null) {
            root = layer;
            while (root != null) {
                if (root.left != null) root.left.next = root.right;
                if (root.right != null && root.next != null) root.right.next = root.next.left;
                root = root.next;
            }
            layer = layer.left;
        }        
    }
}

第七题 117. Populating Next Right Pointers in Each Node II

题目描述

现在情况仍然一样，只是二叉树并不是完全平衡的二叉树。

算法

利用三个指针，分别记录下head的位置，然后上一个的位置。之后找到合适的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
public class Solution {
    public void connect(TreeLinkNode root) {
        TreeLinkNode head = null;
        TreeLinkNode prev = null;
        TreeLinkNode cur = root;
        while (cur != null) {
            //The same layer
            while (cur != null) {
                if (cur.left != null) {
                    if (prev == null) {
                        head = cur.left;
                    } else {
                        prev.next = cur.left;
                    }
                    prev = cur.left;
                }
                if (cur.right != null) {
                    if (prev == null) {
                        head = cur.right;
                    } else {
                        prev.next = cur.right;
                    }
                    prev = cur.right;
                }
                cur = cur.next;
            }
            cur = head;
            head = null;
            prev = null;
        }        
    }
}

第八题 112. Path Sum

题目描述

在一课树种，查看从root到叶节点，有没有值等于target的路径，如果有，返回true否则返回false

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class hasPathSum112 {
    public boolean hasPathSum(TreeNode root, int sum) {
        return helper(root, sum, 0);
    }
    public boolean helper(TreeNode root, int sum, int cur) {
        if (root == null) return false;
        cur += root.val;
        if (sum == cur && root.left == null && root.right == null) return true;
        boolean right = false, left = false;
        if (root.left != null)
            left = helper(root.left, sum, cur);
        if (root.right != null)
            right = helper(root.right, sum, cur);
        return left || right;
    }
}

第九题 113. Path Sum II

题目描述

现在需要找出所有的等于target的路径

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class pathSum113 {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res = new ArrayList<>();
        helper(res, new ArrayList<>(), root, 0, sum);
        return res;
    }
    public void helper(List<List<Integer>> res, List<Integer> temp, TreeNode root, int cur, int sum) {
        if (root == null) return;
        cur += root.val;
        if (cur == sum && root.left == null && root.right == null) {
            temp.add(root.val);
            res.add(new ArrayList<>(temp));
            temp.remove(temp.size() - 1);
            return;
        }
        temp.add(root.val);
        if (root.left != null) helper(res, temp, root.left, cur, sum);
        if (root.right != null) helper(res, temp, root.right, cur, sum);
        temp.remove(temp.size() - 1);
    }
}