Flatten Binary Tree to Linked List && Generate Parentheses && Gray Code

Flatten太简单了 递归 一遍过 oh yeah = = 也没什么好骄傲的

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void flatten(TreeNode root) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if (root == null)
            return;
        TreeNode left = root.left;
        TreeNode right = root.right;
        flatten(left);
        flatten(right);
        root.left = null;
        root.right = left;
        TreeNode iter = root;
        while (iter.right != null)
            iter = iter.right;
        iter.right = right;
    }
}

括号那题可以看成多个节点组成一个森林，这样想来可以用递归来做。但是想了一下计算量太多（重复太多），所以用递推——动规来做
S(n) = S(0)*S(n-1) + S(1)*S(n-2) + …… + S(n-1)*S(0)
。。。。结果发现不是计算长度而是生成字符串。。。。不过也可以用递推吧

public class Solution {
    ArrayList<ArrayList<String>> lists = new ArrayList<ArrayList<String>>();
    
    public ArrayList<String> generateParenthesis(int n) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<String> results = new ArrayList<String>();
        if (n == 0){
            results.add("");
            return results;
        }
            
        if (lists.size() < n){
            ArrayList<String> temp = generateParenthesis(n-1);
            lists.add(temp);
        }
        ArrayList<String> children;
        ArrayList<String> friends;
        for (int i = 0; i < n; ++i){
            children = new ArrayList<String>();
            friends = new ArrayList<String>();
            children.addAll(lists.get(i));
            friends.addAll(lists.get(n-1-i));
            for (int j = 0; j < children.size(); ++j){
                children.set(j, "(" + children.get(j) + ")");
                for (int k = 0; k < friends.size(); ++j)
                    results.add(children.get(j) + friends.get(k));
            }
        }
        return results;
    }
}

不知道为什么会runtime error，明天起来查吧 sigh

窘 发现是 for (int k = 0; k < friends.size(); ++j)最后k写成了j
然后觉得还是把lists放在函数里面比较好？当然试验了以下里面和外面都行。

import java.util.ArrayList;

public class Solution {    
    public ArrayList<String> generateParenthesis(int n) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<ArrayList<String>> lists = new ArrayList<ArrayList<String>>();
        ArrayList<String> results = new ArrayList<String>();
        if (n == 0){
            results.add("");
            return results;
        }
            
        for (int i = 0; i < n; ++i){
            ArrayList<String> temp = generateParenthesis(i);
            lists.add(temp);
        }
        ArrayList<String> children;
        ArrayList<String> friends;
        for (int i = 0; i < n; ++i){
            children = new ArrayList<String>();
            friends = new ArrayList<String>();
            children.addAll(lists.get(i));
            friends.addAll(lists.get(n-1-i));
            for (int j = 0; j < children.size(); ++j){
                children.set(j, "(" + children.get(j) + ")");
                for (int k = 0; k < friends.size(); ++k)
                    results.add(children.get(j) + friends.get(k));
            }
        }
        return results;
    }
}

格雷码发现了一个规律，高位增加1之后，低位总是反过来一遍就能和原来组成新的多位格雷码。

public class Solution {
    public ArrayList<Integer> grayCode(int n) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<Integer> results = new ArrayList<Integer>();
        results.add(0);
        if (n == 0)
            return results;
        results.add(1);
        if (n == 1)
            return results;
        for (int i = 2; i <= n; ++i){
            int size = results.size(); 
            int high = 1 << (i-1);
            for (int j = size-1; j >= 0; j--)
                results.add(high + results.get(j));
        }
        return results;
    }
}

不过还是没有一遍过，又是循环中i写成了n这种错误，sigh，以后要注意阿。。。