Divide and Conquer

404. Sum of Left Leaves

3
/
9 20
/
15 7

There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.

多种做法都可以，BFS，stack和分治。判断叶子节点就行，不用绕，多想。

   public int sumOfLeftLeaves(TreeNode root) {
       if (root == null) {
           return 0;
       } 
       int res = 0;
       if (root.left != null) {
           // leaf node
           if (root.left.left == null && root.left.right == null) {
               res += root.left.val;
           } else {
               // not leaf node
               res += sumOfLeftLeaves(root.left);
           }
       }
       res += sumOfLeftLeaves(root.right);
       return res;
   }

    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null || root.left == null && root.right == null) return 0;
        
        int res = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while(!queue.isEmpty()) {
            TreeNode curr = queue.poll();

            if(curr.left != null && curr.left.left == null && curr.left.right == null) res += curr.left.val;
            if(curr.left != null) queue.offer(curr.left);
            if(curr.right != null) queue.offer(curr.right);
        }
        return res;
    }

235. Lowest Common Ancestor of a Binary Search Tree

return的是node，一开始没想明白

678. Valid Parenthesis String

题目就是有（ * ）三种字符，*可以代表字符或左右括号，判断一个输入字符是不是合法的

题目的复杂程度是由 * 带来的。
首先想到在没有的 * 情况下用一个计数器来记录左右括号，只是需要特殊判断”）（“的情况。碰见右括号但是count是0
在有 * 的情况的下，想到用递归去处理 * 带来的三种情况，去调用自己
DFS

class Solution {
    public boolean checkValidString(String s) {
        if (s == null) {
            return false;
        }
        return check(s, 0, 0);
        }
    public boolean check(String s, int start, int count) {
        for (int i = start; i < s.length(); i++) {
            char cur = s.charAt(i);
            if (cur == '(') {
                count++;
            } else if (cur == ')') {
                if (count <= 0) {
                    return false;
                }
                count--;
            } else {
              return check(s, i + 1, count + 1) || check(s, i + 1, count - 1) || check(s, i + 1, count);  
            }
    }
        return count == 0;

    }
}

241. Different Ways to Add Parentheses

2 * 3 - 4 * 5 可以在各处加括号，返回所有可能的结果

每个运算符分成左右两个部分，两部分再递归调用自己，分治！
如何判断进来的是只有数字的字符串比较重要：res的size是0

    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> res = new ArrayList<>();
        if (input == null || input.length() == 0) {
            return res;
        }
        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            if (c == '+' || c == '-' || c == '*') {
                String first = input.substring(0, i);
                String last = input.substring(i + 1);
                List<Integer> res1 = diffWaysToCompute(first);
                List<Integer> res2 = diffWaysToCompute(last);
                // calculate all possible solutions
                for (Integer r1 : res1) {
                    for (Integer r2 : res2) {
                        if (c == '+') {
                            res.add(r1 + r2);
                        } else if (c == '-') {
                            res.add(r1 - r2);
                        } else {
                            res.add(r1 * r2);
                        }
                    } 
                }
            } 

        } 
            // a single number
        if (res.size() == 0) {
            res.add(Integer.valueOf(input));
        }
        return res;
    }

23. Merge k Sorted Lists

class Solution {
    public static ListNode mergeKLists(ListNode[] lists){
        return partion(lists,0,lists.length-1);
    }

    public static ListNode partion(ListNode[] lists,int s,int e){
        if(s==e)  return lists[s];
        if(s<e){
            int q=(s+e)/2;
            ListNode l1=partion(lists,s,q);
            ListNode l2=partion(lists,q+1,e);
            return merge(l1,l2);
        }else
            return null;
    }

    //This function is from Merge Two Sorted Lists.
    public static ListNode merge(ListNode l1,ListNode l2){
        if(l1==null) return l2;
        if(l2==null) return l1;
        if(l1.val<l2.val){
            l1.next=merge(l1.next,l2);
            return l1;
        }else{
            l2.next=merge(l1,l2.next);
            return l2;
        }
    }
}