Binary Tree paths

這題可以用兩種方法，一種是 DFS，一種是 divide and conquer

DFS 就是很一般的解題方法:

public List<String> binaryTreePaths(TreeNode root) {
    List<String> results = new ArrayList<>();
    if (root == null) {
        return results;
    } 

    helper(root, results, String.valueOf(root.val));
    return results;
}

public void helper(TreeNode root, List<String> results, String path) {
    if (root == null) {
        return;
    }

    if (root.left != null) {
        helper(root.left, results, path + "->" + String.valueOf(root.left.val));
    }
    if (root.right != null) {
        helper(root.right, results, path + "->" + String.valueOf(root.right.val));
    }
    if (root.left == null && root.right == null) {
        results.add(path);
    }
    return ;
}

divide & conquer 太久沒用會忘記他的想法，其實就是部分結果也會是整體結果

所以直接分成左邊結果和右邊結果後再把路徑連接起來就是答案了

然後要注意 root 只有一個點的情況

public List<String> binaryTreePaths(TreeNode root) {
    List<String> results = new ArrayList<>();
    if (root == null) {
        return results;
    }

    List<String> leftPaths = binaryTreePaths(root.left);    //divide & conquer left
    List<String> rightPaths = binaryTreePaths(root.right);    //divide & conquer right
    for (String path : leftPaths) {
        results.add(root.val + "->" + path);
    }
    for (String path : rightPaths) {
        results.add(root.val + "->" + path);
    }
    if (root.left == null && root.right == null) {
        results.add("" + root.val);
    }
    return results;
}