P234 二叉树中的所有路径

描述#

这个题目说的是，给你一棵二叉树，你要返回所有从根到叶子节点的路径。

比如说，给你的二叉树是：
1
/   

2     4


8
在这棵二叉树中，从根到叶子节点有两条路径：
[
"1->2->8",
"1->4"
]

代码#

public class AlgoCasts {

  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
      val = x;
    }
  }

  private void dfs(TreeNode root, String path, List<String> result) {
    if (root == null) return;
    path += root.val;
    if (root.left == null && root.right == null) {
      result.add(path);
    } else {
      path += "->";
      dfs(root.left, path, result);
      dfs(root.right, path, result);
    }
  }

  // Time: O(n^2), Space: O(n^2)
  public List<String> binaryTreePaths(TreeNode root) {
    List<String> result = new ArrayList<>();
    dfs(root, "", result);
    return result;
  }

  private void dfsV2(TreeNode root, StringBuilder path, List<String> result) {
    if (root == null) return;
    int len = path.length();
    path.append(root.val);
    if (root.left == null && root.right == null) {
      result.add(path.toString());
    } else {
      path.append("->");
      dfsV2(root.left, path, result);
      dfsV2(root.right, path, result);
    }
    path.setLength(len);
  }

  // Time: O(n*log(n)), Space: O(n)
  public List<String> binaryTreePathsV2(TreeNode root) {
    List<String> result = new ArrayList<>();
    dfsV2(root, new StringBuilder(), result);
    return result;
  }

}