面试刷题咯～每天10道～

我也在刷题，一天一两题的频率，楼主一天十题有点猛

明天就要面试了~~~祝我好运~~~锦鲤~~~~~保佑我🙏

伤心，感觉挂了....寒假又要开始刷题了。。。

soliloquyyy 发表于 2018-12-19 09:16
伤心，感觉挂了....寒假又要开始刷题了。。。

别丧啊。努力都不会白费的

shaonan 发表于 2018/12/20 08:07:05


别丧啊。努力都不会白费的

啊…感谢感谢。昨晚伤心了一会儿，今天开始恢复刷题了～

寒假跟进楼主刷题 加油

今天10道刷完了。今天是按照tree的tag来的
Leetcode 96 Unique Binary Search Tree 1
这道题是要返回有多少个不同结果的tree.这种题一看就是可以用dp来解决。dp[i]在这代表的含义是当n=i的时候能够生成多少个tree。我们的initial condition是dp[0] = 1, dp[1] = 1.dp[2] = 2。一个node和没有node都只有一种形式。首先我们可以想想，当n=3, 我们分别以1，2，3为root，然后把他们数量加起来就是最终结果。
那么当以1为root时，因为是BST，所以没有比1小的数，也就是left subtree有0个，right subtree有2个。我们用dp[0]*dp[2]. 我们之所以能用dp是因为subtree的构建过程是一样的。root为2时，左边有1个，右边有1个。dp[1]*dp[1]. 以此类推。

1. class Solution {
   
2.     public int numTrees(int n) {
   
3.         int[] dp = new int[n+1];
   
4.         if(n <= 1)
   
5.             return 1;
   
6.         dp[0] = 1;
   
7.         dp[1] = 1;
   
8.         dp[2] = 2;
   
9.         
   
10.         
    
11.         int sum = 0;
    
12.         for(int i=3;i<=n;i++)
    
13.         {
    
14.             for(int j=1;j<=i;j++)
    
15.                 dp[i] += dp[j-1] * dp[i-j];  
    
16.         }
    
17.         
    
18.         return dp[n];
    
19.     }
    
20. }
    

复制代码

Unique Binary Search Tree 2
这道题就不能用dp了，因为我们需要generate所有的tree，而不是一个数字。
我们以1...n中的每个数来最root，然后因为我们是bst，所以我们的left subtree的大小是肯定小于root的。假设我们有一个数k是在1...n中间的，那么我们k为root的left subtree范围是1...k-1个, right subtree 是k+1...n。这样我们就能够用一个boundary来限制。

1. class Solution {
   
2.     public List<TreeNode> generateTrees(int n) {
   
3.         return helper(1,n);
   
4.     }
   
5.    
   
6.     public List<TreeNode> helper(int min, int max)
   
7.     {
   
8.         List<TreeNode> res = new ArrayList<>();
   
9.         if(min > max)
   
10.             return res;
    
11.         
    
12.         for(int i=min;i<=max;i++)
    
13.         {
    
14.             List<TreeNode> left_tree = helper(min,i-1);
    
15.             List<TreeNode> right_tree = helper(i+1,max);
    
16. 
    
17.             if(left_tree.size() == 0 && right_tree.size() == 0)
    
18.             {
    
19.                 TreeNode root = new TreeNode(i);
    
20.                 res.add(root);
    
21.                 return res;
    
22.             }
    
23.             else if(right_tree.size() == 0)
    
24.             {
    
25.                 for(TreeNode left: left_tree)
    
26.                 {
    
27.                     TreeNode root = new TreeNode(i);
    
28.                     root.left = left;
    
29.                     res.add(root);
    
30.                 }
    
31.             }
    
32. 
    
33.             else if(left_tree.size() == 0)
    
34.             {
    
35.                 for(TreeNode right: right_tree)
    
36.                 {
    
37.                     TreeNode root = new TreeNode(i);
    
38.                     root.right = right;
    
39.                     res.add(root);
    
40.                 }
    
41.             }
    
42.             else
    
43.             {
    
44.                 for(TreeNode right: right_tree)
    
45.                 {
    
46.                     for(TreeNode left: left_tree)
    
47.                     {
    
48.                         TreeNode root = new TreeNode(i);
    
49.                         root.right = right;
    
50.                         root.left = left;
    
51.                         res.add(root);
    
52.                     }
    
53.                 }
    
54.             }
    
55.             
    
56.         }
    
57.         return res;
    
58.     }
    
59. }

复制代码

明天应该刷完题就写解释。今天是一直刷，想着最后解释，发现解释太多。
今天就放题目好了。
Recover Binary search tree
Binary tree zigzag level order traversal
Construct a binary tree from preorder & inorder traversal
Construct a binary tree from postorder & inorder traversal
Binary Tree level order traversal 2
balanced binary tree
minimum depth of a binary tree
path sum

继续刷tree tag
Leetcode 113. Path Sum II
首先我们知道Path sum只要返回boolean，这道题要换回所有的path（path sum = given sum）.
首先这道题大致思路是一样的。因为这条path必须从root到leaf，我们就判断到left的时候，sum是不是相等。而我们每次地柜呢，就是用sum-root.val.
代码如下

1. /**
   
2. * Definition for a binary tree node.
   
3. * public class TreeNode {
   
4. *     int val;
   
5. *     TreeNode left;
   
6. *     TreeNode right;
   
7. *     TreeNode(int x) { val = x; }
   
8. * }
   
9. */
   
10. class Solution {
    
11.     public List<List<Integer>> pathSum(TreeNode root, int sum) {
    
12.         List<List<Integer>> res = new ArrayList<>();
    
13.         if(root == null)
    
14.             return res;
    
15.         
    
16.         List<Integer> temp_res = new ArrayList<>();
    
17.         helper(root, sum, res, temp_res);
    
18.         return res;
    
19.     }
    
20.    
    
21.     public void helper(TreeNode root, int sum, List<List<Integer>> res, List<Integer> temp_res)
    
22.     {
    
23.         if(root == null)
    
24.             return;
    
25.         
    
26.         temp_res.add(root.val);
    
27.         
    
28.         if(root.left == null && root.right == null && sum == root.val)
    
29.         {     
    
30.             res.add(new ArrayList<Integer>(temp_res));
    
31.             // return;
    
32.         }else
    
33.         {
    
34.             helper(root.left, sum-root.val, res, temp_res);
    
35.             helper(root.right, sum-root.val, res, temp_res);
    
36.         }
    
37.         
    
38.         temp_res.remove(temp_res.size()-1);
    
39.      
    
40. 
    
41.     }
    
42. }

复制代码