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;
    }
}

109. Convert Sorted List to Binary Search Tree[TODO]

Version #2 [TODO]
Count the size once
And take O(n) time to solve


Version #1 Two pointers
Each layer is size 2^depth

for each node, the time to find the slow pointer is O(node length)
Total length is always O(n)
So we need O(nlogn) to solve this problem

53.30 %



public class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        //TODO
        return sortedListToBST(head, null);
    }
    private TreeNode sortedListToBST(ListNode head, ListNode tail) {
        if (head == tail) return null;
        ListNode slow = head;
        ListNode fast = head;
        while (fast != tail && fast.next != tail) {
            slow = slow.next;
            fast = fast.next.next;
        }
        TreeNode root = new TreeNode(slow.val);
        root.left = sortedListToBST(head, slow);
        root.right = sortedListToBST(slow.next, tail);
        return root;
    }
}