LeetCode(22) -- 605, 606, 617

P605. Can Place Flowers (Easy)

种花，不能相邻，求最多还可以种n个吗？

Input: flowerbed = [1,0,0,0,1], n = 1
Output: True

我的思路

1中间的空隙至少是3，才能种一个。但实际上我也可以顺序地往下种，只要左右都是0，就把它变成1。

我的代码

public class E_605_CanPlaceFlowers {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int counter = 0;
        if (flowerbed.length == 1) {
            if (flowerbed[0] == 0) return n <= 1;
            else return n == 0;
        }
        for (int i = 0; i < flowerbed.length; i++) {
            if (flowerbed[i] == 0) {
                if (i == 0) {
                    if (flowerbed[1] == 0) {
                        flowerbed[i] = 1;
                        counter++;
                    }
                } else if (i == flowerbed.length - 1) {
                    if (flowerbed[flowerbed.length - 2] == 0) {
                        flowerbed[i] = 1;
                        counter++;
                    }
                } else {
                    if (flowerbed[i - 1] == 0 && flowerbed[i + 1] == 0) {
                        flowerbed[i] = 1;
                        counter++;
                    }
                }
            }
        }
        return n <= counter;
    }
}

改了两次bug，100%

最优解

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int M = flowerbed.length;
        if (n == 0) return true;

        for (int i = 0; i < flowerbed.length; i++) {
            if (flowerbed[i] == 0) {
                if ((i == 0 || flowerbed[i - 1] == 0) && (i == M - 1 || flowerbed[i + 1] == 0)){
                    if (--n == 0) return true;
                    flowerbed[i] = 1;
                    i++;
                }
            }
        }
        return false;
    }
}

正常情况下只在判断前一个和后一个为0，如果是第一个，跟前面为0是等价的。

P606. Construct String from Binary Tree (Easy)

前序遍历一棵树，用字符串表示这棵树。不必要的括号要省略掉

我的思路

省略括号的逻辑是，只有在当前子节点不是空，或者右边有节点必须用括号来占位置时，才加括号并遍历子节点。

我的代码

public class E_606_ConstructStringfromBinaryTree {
    StringBuilder sb = new StringBuilder();
    public String tree2str(TreeNode t) {
        dfs(t);
        return sb.toString();
    }

    private void dfs(TreeNode node) {
        if (node == null) {
            return;
        }
        sb.append(node.val);
        if (node.left != null || node.right != null) {
            sb.append("(");
            dfs(node.left);
            sb.append(")");
        }
        if (node.right != null) {
            sb.append("(");
            dfs(node.right);
            sb.append(")");
        }
    }
}

100%

最优解

class Solution {
    public String tree2str(TreeNode t) {
        if(t == null) return "";
        StringBuilder sb = new StringBuilder();
        tree2str(t,sb);
        return sb.toString();
    }
    public void tree2str(TreeNode t, StringBuilder sb) {
        if(t.left == null && t.right == null) {
            sb.append(t.val);
            return;
        }
        sb.append(t.val);
        if(t.left == null) {
            sb.append("()");
        } else {
            sb.append("(");
            tree2str(t.left, sb);
            sb.append(")");
        }
        if(t.right != null) {
            sb.append("(");
            tree2str(t.right, sb);
            sb.append(")");
        }
    }
}

差不多。

P617. Merge Two Binary Trees (Easy)

合并两棵树。

我的思路

递归

我的代码

public class E_617_MergeTwoBinaryTrees {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) {
            return null;
        }
        if (t1 == null) {
            return t2;
        }
        if (t2 == null) {
            return t1;
        }
        TreeNode root = new TreeNode(t1.val + t2.val);
        root.left = mergeTrees(t1.left, t2.left);
        root.right = mergeTrees(t1.right, t2.right);
        return root;
    }
}

67%

最优解

class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if(t1==null)return t2;
        if(t2==null)return t1;

        TreeNode result = new TreeNode(t1.val+t2.val);
        result.left = mergeTrees(t1.left,t2.left);
        result.right = mergeTrees(t1.right,t2.right);

        return result;
    }
}

基本跟我的完全一样，只是省略了第一步。