Java Spring Basic [Uber]

Spring User Authentication & Authorization

-->
import.sql file will ensure that data will be loaded into the database when we boot our application

-->

dependencies {
   compile 'org.springframework.boot:spring-boot-starter-thymeleaf'    compile 'org.springframework:spring-orm:4.2.4.RELEASE'    compile 'org.springframework.data:spring-data-jpa:1.9.2.RELEASE'    compile 'org.hibernate:hibernate-core:5.0.6.Final'    compile 'org.hibernate:hibernate-entitymanager:5.0.6.Final'   compile 'org.apache.tomcat:tomcat-dbcp:8.0.30'   compile 'org.springframework.boot:spring-boot-starter-security'   compile 'org.thymeleaf.extras:thymeleaf-extras-springsecurity4:2.1.2.RELEASE'
   runtime 'com.h2database:h2'    runtime 'javax.transaction:jta:1.1'    runtime 'org.aspectj:aspectjweaver:1.8.7'
   testCompile 'org.springframework.boot:spring-boot-starter-test'}

-->Authentication
Verifying that a user is who she or he is claiming to be.
User implements UserDetails

-->Authorization
Verifying that an authenticated user has permission to perform the requested operation.
Verifying that if he is allowed to access a requested resource or perform a requested action.

-->

@Overridepublic Collection<? extends GrantedAuthority> getAuthorities() {
    List<GrantedAuthority> authorities = new ArrayList<>();    authorities.add(new SimpleGrantedAuthority(role.getName()));    return authorities;}

-->
role-id是map到role的entry name

@OneToOne@JoinColumn(name = "role_id")
private Role role;

-->Spring Data JPA
So all we have to do here is extend CrudRepository
Auto generate the method

@Repositorypublic interface UserDao extends CrudRepository<User,Long> {
    User findByUsername(String username);}

-->SecutiryConfig

@EnableWebSecurity

SecutiryConfig extends WebSecurityConfigurerAdapter

Spring Security Filter Chain

This chain allows us to filter certain requests so that a user doesn't have to be authenticated...

Linux Command

//-->run shell script
chmod +x ./run.sh
./run.sh

//-->download
wget https://baidu.com/index.html
...

//-->ssh copy
//upload file to server [scp #port local_path user@ip:server_path]
scp -P22 ~/test.txt root@192.168.31.193:~/tmp/

//download [scp user@ip:server_path local_path]
//download directory [scp -r user@ip:server_path local_path]

Spring-Hibernate

Which component will fetch model data, supply that data to views, as well as handle the routing of incoming requests?
Controller

Controller ----->  Service -----> DAO-Data Access Object(Repository) -----> SessionFactory

Starting Your Database Server

With a terminal window open in the directory of your project that contains the H2 JAR file, the command to start your server is as follows:

java -cp h2*.jar org.h2.tools.Server

After this, a browser tab should open, and in that tab you'll need to enter the database connection URL, username and password. These should match what you have in your app.properties file.

@OneToMany(mappedBy = "category")
private List<Gif> gifs = new ArrayList<>();

mappedBy后面有一个变量fetch默认value为fetchtype.lazy
可以改成fetchtype.eager -> Every time one or more categories are fetched from the database, another query will be performed to fetch all GIF entities from the database that are associated with that category.
但是如果直接设成eager，那么即使在category index page，没有的GIFs也会被fetch
So we fetch all the GIFs for a category, only when a single category is being fetched.

@Overridepublic Category findById(Long id) {
    Session session = sessionFactory.openSession();    Category category = session.get(Category.class, id);    Hibernate.initialize(category.getGifs());    session.close();    return category;}

We were seeing that error because we tried to access a mapped collection outside of a hibernate session, which just isn't possible. 所以加入一句Hibernate.initialize(category.getGifs());

// Mark/unmark an existing GIF as a favorite@RequestMapping(value = "/gifs/{gifId}/favorite", method = RequestMethod.POST)
public String toggleFavorite(@PathVariable Long gifId, HttpServletRequest request) {
    // TODO: With GIF whose id is gifId, toggle the favorite field    Gif  gif = gifService.findById(gifId);    gifService.toggleFavourate(gif);    // TODO: Redirect to GIF's detail view    return String.format("redirect:%s", request.getHeader("referer"));}

• If you throw this in as a parameter to a controller method,
• 3:13
  it exposes all sorts of stuff related to the HTTP request including
• 3:17
  all of its headers that you recall from the HTTP basics course.
• 3:23
  One of the headers it exposes is what's called the referer header here.
• 3:29
  Check the teachers notes for the misspelling on this.
• 3:31
  This is actually the correct use.
• 3:34
  Now this referer header allows you to see what URL the user or request or
• 3:39
  was on when the HTTP request was made.
• 3:42
  In essence, it allows us to see where this request came from.
• 3:45
  So that in our case, I can send the browser right back there for the redirect.
• 3:50
  And I did this because a user might mark a GIF as a favorite from the detail or
• 3:54
  from the index view and this takes the browser back to wherever it came from.
• 3:59
  Now word of warning about this and I do want to be clear about this warning.
• 4:04
  Using a client specified value can be dangerous.
• 4:09
  If the user's browser is compromised,
• 4:12
  malicious software could set the referer to a malicious site.
• 4:17
  And suddenly our application sends the user into a danger zone
• 4:21
  simply when they mark or unmark a GIF as a favorite.
• 4:25
  So be careful.

Lint 201.Segment Tree Build

The structure of Segment Tree is a binary tree which each node has two attributes start and end denote an segment / interval.

start and end are both integers, they should be assigned in following rules:

• The root's start and end is given by build method.
• The left child of node A has start=A.left, end=(A.left + A.right) / 2.
• The right child of node A has start=(A.left + A.right) / 2 + 1, end=A.right.
• if start equals to end, there will be no children for this node.

Implement a build method with two parameters start and end, so that we can create a corresponding segment tree with every node has the correct start and end value, return the root of this segment tree.

/**
 * Definition of SegmentTreeNode:
 * public class SegmentTreeNode {
 *     public int start, end;
 *     public SegmentTreeNode left, right;
 *     public SegmentTreeNode(int start, int end) {
 *         this.start = start, this.end = end;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     *@param start, end: Denote an segment / interval
     *@return: The root of Segment Tree
     */
    public SegmentTreeNode build(int start, int end) {
        // write your code here
        if (start > end) return null;
        SegmentTreeNode result = new SegmentTreeNode(start, end);
        if (start == end) return result;
        int mid = (start + end) / 2;
        SegmentTreeNode left = build(start, mid);
        SegmentTreeNode right = build(mid + 1, end);
        result.left = left;
        result.right = right;
        return result;
    }
}

331. Verify Preorder Serialization of a Binary Tree

推荐Version #2

Version #4 Using stack [better version]
explanation直接看code里面的comment也可以
没有Version #3那么无脑，基本思路是一直的，就是一直砍leaf然后将它们的parent退化成新的leaf
速度比Version #3好一点点

用stack模拟了对tree的根-左-右traversal的操作
[1]如果是数字，就push
[2]如果是#，看一下它的上一个是不是#
  case1 上一个点是#： 证明走到了leaf, pop两次
                       可以保证不会出现#,#,#(curr)连续的情况，因为一旦有两个连续#就会进行pop操作，所以一定是x,#,#(curr)
                        pop之后(见[3])
  case2 上一个点不是#： 证明现在的'#'是一个node的left child -> push curr

[3]对于[2].case1，有两种情况
   case1 上一个点是#，证明当前的x,#,# -> # 将它的parent退化成了一个新的leaf, 可以继续pop
   case2 上一个点是node，证明当前的x,#,# -> #是一个left child，此时重新push一个“#”

一旦出现pop或者peek不出来的情况，就可以直接返回false了，证明之前没有traverse到足够的点与当前的点组成valid part
最后剩下的是一个“#”


"when you iterate through the preorder traversal string, for each char:

case 1: you see a number c, means you begin to expand a new tree rooted with c, you push it to stack

case 2.1: you see a #, while top of stack is a number, you know this # is a left null child, put it there as a mark for next coming node k to know it is being the right child.

case 2.2: you see a #, while top of stack is #, you know you meet this # as right null child, you now cancel the sub tree (rooted as t, for example) with these two-# children. But wait, after the cancellation, you continue to check top of stack is whether # or a number:

---- if a number, say u, you know you just cancelled a node t which is left child of u. You need to leave a # mark to the top of stack. So that the next node know it is a right child.

---- if a #, you know you just cancelled a tree whose root, t, is the right child of u. So you continue to cancel sub tree of u, and the process goes on and on."

 14.07 %
public class Solution {
    public boolean isValidSerialization(String preorder) {
        if (preorder == null || preorder.length() == 0) return true;
        String[] nodes = preorder.split(",");
        Stack<String> stack = new Stack<>();
        for (String curr : nodes) {
            if (!curr.equals("#")) {
                stack.push(curr);
            } else {
                // curr == "#" and it is a right child of a leaf node
                while (!stack.isEmpty() && stack.peek().equals("#")) {
                    stack.pop();
                    if (stack.isEmpty()) return false;
                    stack.pop();
                    //go back to the while loop to check if its a left child or a right child
                }
                // curr == "#" and it is a left child of a node
                //we still need to push it back to the stack
                stack.push(curr);
            }
        }
        return stack.size() == 1 && stack.peek().equals("#");
    }
}



Version #3 Using stack
比较无脑的方法, 每次都push, 一看到leaf就往外pop
需要做stack.get()理论上来说是不属于stack这个数据结构的操作
version #4更elegant一点

Time O(#nodes)
Space O(#nodes)
4.56 %
//A leaf node must be "node", "#", "#"
//we can use a "#" to substitude the leaf node
//There will only be 1 "#" in the end
public class Solution {
    public boolean isValidSerialization(String preorder) {
        if (preorder == null || preorder.length() == 0) return true;
        String[] nodes = preorder.split(",");
        Stack<String> stack = new Stack<>();
        for (String node : nodes) {
            stack.push(node);
            while (stack.size() >= 3) {
                int size = stack.size();
                if (stack.get(size - 1).equals("#") && stack.get(size - 2).equals("#") && !stack.get(size - 3).equals("#")) {
                    for (int i = 0; i < 3; i++) {
                        stack.pop();
                    }
                    stack.push("#");
                } else break;
            }
        }
        return stack.size() == 1 && stack.peek().equals("#");
     
    }
}


Version #2

Count #nodes and #pound signs(null)

Eventually #Nodes + 1 == #("#")
For every moment, #Nodes + 1 >= #("#")
上面是算法哥讲的
判断依据是
Since it is a preorder traversal, the root nodes are always visited before their '#' children
所以node个数 + 1 一直是大于 pound sign个数，最后达到相等模糊
我觉得这个说法稍显模糊


LC上一个答案写的比较好
把二叉树看成一个directed graph
for every moment
    outdegree  >= indegree
otherwise we will have some hanging points

“In a binary tree, if we consider null as leaves, then

• all non-null node provides 2 outdegree and 1 indegree (2 children and 1 parent), except root
• all null node provides 0 outdegree and 1 indegree (0 child and 1 parent).

Suppose we try to build this tree. During building, we record the difference between out degree and in degree diff = outdegree - indegree. When the next node comes, we then decrease diffby 1, because the node provides an in degree. If the node is not null, we increase diff by 2, because it provides two out degrees. If a serialization is correct, diff should never be negative and diff will be zero when finished.”

一开始写是在每一个state结束以后判断outdegree-indegree < 0
有一个case跑不过

"#,7,6,9,#,#,#"

当7来的时候并没有indegree可以consum，所以应该在每个Node来的时刻判断

52.53 %
public class Solution {
    public boolean isValidSerialization(String preorder) {
        if (preorder == null || preorder.length() == 0) return true;
        //root doesn't have any indegree
        int indegree = -1;
        int outdegree = 0;
        String[] nodes = preorder.split(",");
        for (String curr : nodes) {
            //every coming node consumes 1 indegree
            indegree++;
            if (outdegree - indegree < 0) return false;
            if (!curr.equals("#")) outdegree += 2;        
        }
        return outdegree == indegree;
    }
}


Version #1 Reconstruct BST
实在懒得再写了
但是这个思路很值得学习

298. Binary Tree Longest Consecutive Sequence

549. Binary Tree Longest Consecutive Sequence II
88.64 % 
只考虑由上向下increasing的情况
public class Solution {
    private int max = 0;
    public int longestConsecutive(TreeNode root) {
        if (root == null) return 0;
        //TODO
        longestConsecutiveHelper(root);
        return max;
    }
    private int longestConsecutiveHelper(TreeNode root) {
        if (root == null) return 0;
        int left = longestConsecutiveHelper(root.left);
        int right = longestConsecutiveHelper(root.right);
        int length = 0;
        if (root.left != null && root.left.val == root.val + 1) {
            length = left;
        }
        if (root.right != null && root.right.val == root.val + 1) {
            length = Math.max(length, right);
        }
        length += 1;
        max = Math.max(max, length);
        return length;
    }
}

250. Count Univalue Subtrees

三刷

100.00 %
class Solution {
    public int countUnivalSubtrees(TreeNode root) {
        int[] count = new int[1];
        helper(root, count);
        return count[0];
    }
    // Add current subtree to result
    // Return if current subtree is a univalsubtree
    private boolean helper(TreeNode node, int[] count) {
        if (node == null) {
            return true;
        }
        if (node.left == null && node.right == null) {
            count[0]++;
            return true;
        }
        boolean left = helper(node.left, count);
        boolean right = helper(node.right, count);
        if ((node.left == null || node.left.val == node.val && left)
           && (node.right == null || node.right.val == node.val && right)) {
            count[0]++;
            return true;
        }
        return false;
    }
}


Version #2(better)
12.05 % 

public class Solution {
    private int count;
    public int countUnivalSubtrees(TreeNode root) {
        //current node is the root of a UnivalSubtree:
        //left &  right children are (null || UnivalSubtrees) & value equals to current node
        //return boolean -> is not UnivalSubtree
        if (root == null) return 0;
        count = 0;
        countUnivalSubtreesHelper(root);
        return count;
    }
    private boolean countUnivalSubtreesHelper(TreeNode root) {
        if (root == null) return true;
        boolean left = countUnivalSubtreesHelper(root.left);
        boolean right = countUnivalSubtreesHelper(root.right);
        if (left && right) {
            if ((root.left == null || root.left.val == root.val) && (root.right == null || root.right.val == root.val)) {
                count += 1;
                return true;
            }
        }
        return false;
    }
}

Version #1
对leaf的判断写的不够简洁，其实这道题直接把base case交给root == null就可以了
更新版看Version #2
12.05 % 
public class Solution {
    private int count;
    public int countUnivalSubtrees(TreeNode root) {
        //current node is the root of a UnivalSubtree:
        //left &  right children are (null || UnivalSubtrees) & value equals to current node
        //return boolean -> is not UnivalSubtree
        if (root == null) return 0;
        count = 0;
        countUnivalSubtreesHelper(root);
        return count;
    }
    private boolean countUnivalSubtreesHelper(TreeNode root) {
        if (root.left == null && root.right == null) {
            count += 1;
            return true;
        }
        boolean left = root.left == null ? true : countUnivalSubtreesHelper(root.left);
        boolean right = root.right == null ? true : countUnivalSubtreesHelper(root.right);
        if (left && right) {
            if ((root.left == null || root.left.val == root.val) && (root.right == null || root.right.val == root.val)) {
                count += 1;
                return true;
            }
        }
        return false;
    }
}

241. Different Ways to Add Parentheses

二刷 07/2022

Version #1 Recursion

看起来是medium的题结果竟然没做出来

一开始写了好久都写不对，我自己的写法是在recursion里面一直expand当前的值，然后和后面subresult的结果combine在一起，这里的问题是

((2*(3-4))*5) = -10 

(2*((3-4)*5)) = -10 

里面的 ((2*(3-4))*5) 永远都不会被算到，因为前半部分永远是顺序的2 * 3 - 4

正确做法是每次把当前string分成operator的左右两半

Time - 感觉outer loop应该是所有substring遍历一遍的复杂度，就是O(N^2), inner loop是substring O(N)另外还有iterate over two sub lists to compute their combination results O(N^2)所以大概是O(n^4)?

Space O(N^2) for all substrings

Runtime: 2 ms, faster than 92.07% of Java online submissions for Different Ways to Add Parentheses.

Memory Usage: 41.8 MB, less than 94.00% of Java online submissions for Different Ways to Add Parentheses.

class Solution {

    public List<Integer> diffWaysToCompute(String expression) {

        return compute(expression, new HashMap<>());

    }

    

    private List<Integer> compute(String exp, Map<String, List<Integer>> mem) {

        if (mem.containsKey(exp)) {

            return mem.get(exp);

        }

        boolean isNum = true;

        List<Integer> result = new ArrayList<>();

        for (int i = 0; i < exp.length(); i++) {

            if (!Character.isDigit(exp.charAt(i))) {

                isNum = false;

                List<Integer> res1 = compute(exp.substring(0, i), mem);

                List<Integer> res2 = compute(exp.substring(i + 1), mem);

                for (int num1 : res1) {

                    for (int num2 : res2) {

                        switch (exp.charAt(i)) {

                            case '+':

                                result.add(num1 + num2);

                                continue;

                            case '-':

                                result.add(num1 - num2);

                                continue;

                            case '*':

                                result.add(num1 * num2);

                        }

                    }

                }

            }

        }

        if (isNum) {

            result.add(Integer.valueOf(exp));

        }

        mem.put(exp, result);

        return result;

    }

}

一刷

Add parentheses means give different priority to each operator
char to integer: c - '0'
这里用isDigit来标记是不是纯数字，也可以在最后看subResult.size() == 0，表明也是digit

83.50 %

public class Solution {
    public List<Integer> diffWaysToCompute(String input) {
        if (input == null || input.length() == 0) return new ArrayList<Integer>();
        //TODO
        return diffWaysToCompute(input.toCharArray(), 0, input.length() - 1);
     
    }
    private void compute(char operator, List<Integer> subResult, List<Integer> left, List<Integer> right) {
        for (Integer n1 : left) {
            for (Integer n2 : right) {
                if (operator == '-') subResult.add(n1 - n2);
                if (operator == '+') subResult.add(n1 + n2);
                if (operator == '*') subResult.add(n1 * n2);
            }
        }
    }
    private List<Integer> diffWaysToCompute(char[] str, int start, int end) {
        List<Integer> subResult = new ArrayList<>();
     
        if (start > end) return subResult;
     
        boolean isDigit = true;
        for (int i = start; i <= end; i++) {
            if (str[i] == '+' || str[i] == '-' || str[i] == '*') {
                isDigit = false;
                List<Integer> left = diffWaysToCompute(str, start, i - 1);
                List<Integer> right = diffWaysToCompute(str, i + 1, end);
                compute(str[i], subResult, left, right);
            }
        }
        if (isDigit) {
            int digit = 0;
            for (int i = start; i <= end; i++) {
                digit = digit * 10 + str[i] - '0';
            }
            subResult.add(digit);
        }
        return subResult;
    }
}

222. Count Complete Tree Nodes

二刷
先写了O(n)解法

100.00 %
class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
}

一刷
Brute Force的方法是O(n)
可以根据性质进行优化
每一层O(logn) get height
总共logn层
Time O(logn^2)
           1
        /      \
     1         1
   /   \      /   \
 1    1    1    1


82.17 %


public class Solution {
    /* full tree : #nodex = 2^h - 1
    if (leftHeight == rightHeight) left is full
    if (leftHeight == rightHeight + 1) right is full
    */
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        //count of the root node
        int count = 1;
        //if (root.left == null && root.right == null) return count;
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        if (leftHeight == rightHeight) {
            //left is full
            count += (1 << leftHeight) - 1;
            count += countNodes(root.right);
        } else if (leftHeight == rightHeight + 1) {
            count += (1 << rightHeight) - 1;
            count += countNodes(root.left);
        } else {
            throw new RuntimeException("Invalid Complete Tree");
        }
        return count;
    }
    private int getHeight(TreeNode root) {
        int h = 0;
        while (root != null) {
            root = root.left;
            h++;
        }
        return h;
    }
}

129. Sum Root to Leaf Numbers

二刷
100.00 
class Solution {
    public int sumNumbers(TreeNode root) {
        int[] sum = new int[1];
        if (root != null) {
            helper(root, root.val, sum);
        }
        return sum[0];
    }
   
    private void helper(TreeNode node, int num, int[] sum) {
        if (node.left == null && node.right == null) {
            sum[0] += num;
        } else {
            if (node.left != null) {
                helper(node.left, num * 10 + node.left.val, sum);
            }
            if (node.right != null) {
                helper(node.right, num * 10 + node.right.val, sum);
            }
        }
    }
}


一刷
25.08 %
public class Solution {
    private int sum;
    public int sumNumbers(TreeNode root) {
        sum = 0;
        //TODO
        sumNumbersHelper(root, 0);
        return sum;
    }
    private void sumNumbersHelper(TreeNode root, int path) {
        if (root == null) return;
        path = path * 10 + root.val;
        //leaf node
        if (root.left == null && root.right == null) {
            sum += path;
            return;
        }
        //go to the next layer
        sumNumbersHelper(root.left, path);
        sumNumbersHelper(root.right, path);
    }
}

124. Binary Tree Maximum Path Sum

需要注意localMax无论如何必须包含root.val
即使root.val是负值
19.36 % 
public class Solution {
    private Integer globalMax;
    public int maxPathSum(TreeNode root) {
        globalMax = Integer.MIN_VALUE;
        maxPathSumHelper(root);
        return globalMax;
    }
 
    /*
    global max
    leftSum, rightSum
    */
    private int maxPathSumHelper(TreeNode root) {
        if (root == null) return 0;
        int leftSum = maxPathSumHelper(root.left);
        int rightSum = maxPathSumHelper(root.right);
        int localMax = root.val;
        localMax += leftSum < 0 ? 0 : leftSum;
        localMax += rightSum < 0 ? 0 : rightSum;
     
        globalMax = Math.max(globalMax, localMax);
        return root.val + Math.max(0, Math.max(leftSum, rightSum));
    }
 
}

113. Path Sum II

三刷 06/2022

Time O(N^2) -> O(N) time to copy the path and performs O(N) times -> N is #nodes

Space O(N)

Runtime: 2 ms, faster than 73.40% of Java online submissions for Path Sum II.

Memory Usage: 44.9 MB, less than 31.29% of Java online submissions for Path Sum II.

/**

 * 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 List<List<Integer>> pathSum(TreeNode root, int targetSum) {

        List<List<Integer>> result = new ArrayList<>();

        dfs(root, targetSum, new ArrayList<>(), result);

        return result;

    }

    

    private void dfs(TreeNode node, int targetSum, List<Integer> path, List<List<Integer>> result) {

        if (node == null) {

            return;

        }

        targetSum -= node.val;

        path.add(node.val);

        if (node.left == null && node.right == null) {

            if (targetSum == 0) {

                result.add(new ArrayList<>(path));

            }

            path.remove(path.size() - 1);

            return;

        }

        dfs(node.left, targetSum, path, result);

        dfs(node.right, targetSum, path, result);

        path.remove(path.size() - 1);

    }

}

二刷
100.00 % 
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> result = new ArrayList<>();
        if (root != null) {
            helper(root, sum, new ArrayList<>(), result);
        }
        return result;
    }
    private void helper(TreeNode node, int sum, List<Integer> path, List<List<Integer>> result) {
        path.add(node.val);
        if (node.left == null && node.right == null) {
            if (sum == node.val) {
                result.add(new ArrayList<>(path));
            }
        } else {
            if (node.left != null) {
                helper(node.left, sum - node.val, path, result);
             }
            if (node.right != null) {
                helper(node.right, sum - node.val, path, result);
            }
        }
        path.remove(path.size() - 1);
    }
}
一刷
 46.45 %
public class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> result = new ArrayList<>();
     
        pathSumHelper(root, sum, new ArrayList<>(), result);
        return result;
    }
    private void pathSumHelper(TreeNode root, int sum, List<Integer> path, List<List<Integer>> result) {
        if (root == null) return;
        path.add(root.val);
        if (root.left == null && root.right == null && root.val == sum) {
            result.add(new ArrayList<Integer>(path));
        } else {
            pathSumHelper(root.left, sum - root.val, path, result);
            pathSumHelper(root.right, sum - root.val, path, result);
        }
        path.remove(path.size() - 1);
    }
}

112. Path Sum

二刷 06/2022

Runtime: 0 ms, faster than 100.00% of Java online submissions for Path Sum.

Memory Usage: 44.3 MB, less than 12.60% of Java online submissions for Path Sum.

/**

 * 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 boolean hasPathSum(TreeNode root, int targetSum) {

        if (root == null) {

            return false;

        }

        targetSum -= root.val;

        if (root.left == null && root.right == null) {

            return targetSum == 0;

        }

        return hasPathSum(root.left, targetSum) || hasPathSum(root.right, targetSum);

    }

}

一刷

唉又犯这个错误了
每次特指是leaf的时候都不能用root == null作为终止条件
而应该用root.left == null && root.right == null作为终止条件
13.08 %

public class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) return false;
        //leaf node
        if (root.left == null && root.right == null && root.val == sum) return true;
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}

111. Minimum Depth of Binary Tree

二刷
100.00 % 
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        int min = 0;
        if (root.left == null && root.right == null) {
            min = 0;
        } else if (root.left == null) {
            min = minDepth(root.right);
        } else if (root.right == null) {
            min = minDepth(root.left);
        } else {
            min = Math.min(minDepth(root.left), minDepth(root.right));
        }
        return min + 1;
    }
}


一刷
看着很简单但是还是有坑的

不能无脑取Min
因为如果 root有一个child是null，另一个child很深，就会返回1但是并不是leaf to root
所以要有一个判断，如果一个child depth是0就要返回另外一个
只有当两个都不是0的时候才取min
16.41 %
public class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        if (left == 0) return right + 1;
        if (right == 0) return left + 1;
        return Math.min(left, right) + 1;
    }
}

110. Balanced Binary Tree

二刷 05/2022

Version #1 Top-down version (worse)

Time O(nlogn)

Space O(n) The recursion stack may contain all nodes if the tree is skewed.

Runtime: 2 ms, faster than 26.81% of Java online submissions for Balanced Binary Tree.

Memory Usage: 44.6 MB, less than 34.01% of Java online submissions for Balanced Binary Tree.

/**

 * 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 boolean isBalanced(TreeNode root) {

        // Top-down recursion

        // create a height function

        // Each level takes O(n) time to proceed

        // Worst case time complexity:

        // O(n) + 2 * O(n/2) + 4 * O(n / 4) + ...

        // = O(nlogn)

        // In a skewed-tree, the algorithm is O(n) since it only checks the height of the first two subtrees

        if (root == null) {

            return true;

        }

        return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);

    }

    

    private int height(TreeNode node) {

        if (node == null) {

            return 0;

        }

        return 1 + Math.max(height(node.left), height(node.right));

    }

}

Version #2 Bottom-up (better)

Time O(n) - each node is visited twice

Space O(n)

Runtime: 1 ms, faster than 95.05% of Java online submissions for Balanced Binary Tree.

Memory Usage: 41.6 MB, less than 96.98% of Java online submissions for Balanced Binary Tree.

/**

 * 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 {

    class TreeInfo {

        public int height;

        public boolean isBalanced;

        public TreeInfo(int height, boolean isBalanced) {

            this.height = height;

            this.isBalanced = isBalanced;

        }

    }

    public boolean isBalanced(TreeNode root) {

        TreeInfo info = isBalancedHelper(root);

        return info.isBalanced;

    }

    

    private TreeInfo isBalancedHelper(TreeNode node) {

        if (node == null) {

            return new TreeInfo(0, true);

        }

        TreeInfo leftInfo = isBalancedHelper(node.left);

        if (!leftInfo.isBalanced) {

            return new TreeInfo(-1, false);

        }

        TreeInfo rightInfo = isBalancedHelper(node.right);

        if (!rightInfo.isBalanced) {

            return new TreeInfo(-1, false);

        }

        boolean isBalanced = Math.abs(leftInfo.height - rightInfo.height) <= 1;

        if (!isBalanced) {

            return new TreeInfo(-1, isBalanced);

        }

        return new TreeInfo(1 + Math.max(leftInfo.height, rightInfo.height), isBalanced);

    }

}

一刷

Every node is visited twice
Total time O(#nodes)
69.68 %
public class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        return isBalancedHelper(root) != -1;
    }
    public int isBalancedHelper(TreeNode root) {
        //-1 represents that the subtree is not balanced
        if (root == null) return 0;
        int left = isBalancedHelper(root.left);
        int right = isBalancedHelper(root.right);
        if (left == -1 || right == -1 || Math.abs(left - right) > 1) return -1;
        return Math.max(left, right) + 1;
    }
}