Different Ways to Add Parentheses

加括号的不同方式

思路：分治地求出一个运算符的左边部分和右边部分的结果，将它们两两组合运算。优化的方式是用一个hash表记录所有字串的中间结果，避免重复计算。

1 public class Solution { 2     Map
      
       > map = new HashMap
       
        >(); 3     public List
        
          diffWaysToCompute(String input) { 4         if (map.containsKey(input)) { 5             return map.get(input); 6         } 7          8         List
         
           res = new ArrayList
          
           (); 9         if (!(input.contains("+") || input.contains("-") || input.contains("*"))) {10             res.add(Integer.parseInt(input));11             map.put(input, res);12             return res;13         }14         for (int i = 0; i < input.length(); i++) {15             char c = input.charAt(i);16             if (c == '+' || c == '-' || c == '*') {17                 String p1 = input.substring(0, i);18                 String p2 = input.substring(i + 1, input.length());19                 List
           
             res1 = diffWaysToCompute(p1);20 List
            
              res2 = diffWaysToCompute(p2);21 22 for (int n1 : res1) {23 for (int n2 : res2) {24 if (c == '+') {25 res.add(n1 + n2);26 } else if (c == '-') {27 res.add(n1 - n2);28 } else if (c == '*') {29 res.add(n1 * n2);30 }31 }32 }33 }34 }35 map.put(input, res);36 return res;37 }38 }
            
           
          
         
        
       
      

 

 

Invert Binary Tree

反转二叉树

思路1：虽然很简单但是听说homebrew的作者因为没做出这题被谷歌fuck off 了。。所以还是做下吧。。

1 public class Solution { 2     public TreeNode invertTree(TreeNode root) { 3         if (root == null) { 4             return null; 5         } 6         TreeNode left = root.left; 7         TreeNode right = root.right; 8         root.left = invertTree(right); 9         root.right = invertTree(left);10         return root;11     }12 }

思路2：非递归版。用队列做bfs，把每个节点的左右儿子互换。

1 public class Solution { 2     public TreeNode invertTree(TreeNode root) { 3         if (root == null) { 4             return null; 5         } 6         Queue
      
        q = new LinkedList
       
        (); 7         q.offer(root); 8         while (!q.isEmpty()) { 9             TreeNode cur = q.poll();10             TreeNode left = cur.left;11             TreeNode right = cur.right;12             cur.left = right;13             cur.right = left;14             if (left != null) {15                 q.offer(left);16             }17             if (right != null) {18                 q.offer(right);19             }20         }21         return root;22     }23 }
       
      

 

 

Kth Smallest Element in a BST

二叉树的第k小元素

思路：熟悉二叉树中序遍历的非递归版，这道题就很好做。首先找到最小元素，一定是沿着左子树走到头，然后找次小元素，如果最小节点有右子树，则相当于找右子树的最小元素，如果没有则次小元素为最小元素的父亲。之后的k个元素都这么找。

1 public class Solution { 2     public int kthSmallest(TreeNode root, int k) { 3         Stack
      
        s= new Stack
       
        (); 4         TreeNode cur = root; 5         while (cur != null) { 6             s.push(cur); 7             cur = cur.left; 8         } 9         10         cur = s.pop();11         for (int i = 2; i <= k; i++) {12             if (cur.right != null) {13                 cur = cur.right;14                 while (cur != null) {15                     s.push(cur);16                     cur = cur.left;17                 }18             }19             cur = s.pop();20         }21         return cur.val;22     }23     24 }
       
      

 

 

Lowest Common Ancestor of a Binary Search Tree

二叉查找树的最近公共祖先

思路：与二叉树LCA一样，都是讨论两个节点都在左子树，都在右子树，分别在两边这三种情况。

1 public class Solution { 2     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { 3         if (root == null || p == null || q == null) { 4             return null; 5         } 6         if (p.val < root.val && q.val < root.val) { 7             return lowestCommonAncestor(root.left, p, q); 8         } 9         if (p.val > root.val && q.val > root.val) {10             return lowestCommonAncestor(root.right, p, q);11         }12         return root;13         14     }15 }