二叉树的所有路径

题目描述：给定一个二叉树，返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。

示例：
输入：

输出： [“1->2->5”, “1->3”]
解释：所有根节点到叶子节点的路径为: 1->2->5, 1->3

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
  public List<String> binaryTreePaths(TreeNode root) {

  }
}

方法一：递归 / 深度优先搜索

如果当前节点不是叶子节点，则在当前的路径末尾添加该节点，并继续递归遍历该节点的每一个孩子节点。
如果当前节点是叶子节点，则在当前路径末尾添加该节点后我们就得到了一条从根节点到叶子节点的路径，将该路径加入到答案即可。

class Solution {
  public List<String> binaryTreePaths(TreeNode root) {
    List<String> paths = new ArrayList<>();
    constructPaths(root, "", paths);
    return paths;
  }
  private void constructPaths(TreeNode root, String path, List<String> paths){
    if(root == null) return;
    StringBuffer pathSB = new StringBuffer(path);
    pathSB.append(Integer.toString(root.val));
    if(root.left == null && root.right == null) { // 当前节点是叶子节点
      paths.add(pathSB.toString()); // 把路径加入到答案中
    } else {
      pathSB.append("->"); // 当前节点不是叶子节点，继续递归遍历
      constructPaths(root.left, pathSB.toString(), paths);
      constructPaths(root.right, pathSB.toString(), paths);
    }
  }
}

复杂度分析：

时间复杂度：O(N²)，其中 N 表示节点数目。在深度优先搜索中每个节点会被访问一次且只会被访问一次，每一次会对 path 变量进行拷贝构造，时间代价为 O(N)，故时间复杂度为 O(N²)
空间复杂度：O(N²)，其中 N 表示节点数目。除答案数组外我们需要考虑递归调用的栈空间。在最坏情况下，当二叉树中每个节点只有一个孩子节点时，即整棵二叉树呈一个链状，此时递归的层数为 N，此时每一层的 path 变量的空间代价的总和为 O(∑^N_i=1i) = O(N²) 空间复杂度为 O(N²)。最好情况下，当二叉树为平衡二叉树时，它的高度为 logN，此时空间复杂度为 O((logN)²)

执行结果：通过

执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：38.9 MB, 在所有 Java 提交中击败了72.33%的用户

方法二：遍历 / 广度优先搜索

我们维护两个队列，存储节点以及根到该节点的路径。一开始这个队列里只有根节点。在每一步迭代中，我们取出队列中的首节点，如果它是叶子节点，则将它对应的路径加入到答案中。如果它不是叶子节点，则将它的所有孩子节点加入到队列的末尾。当队列为空时广度优先搜索结束，我们即能得到答案。

class Solution {
  public List<String> binaryTreePaths(TreeNode root) {
    List<String> paths = new ArrayList<String>();
    if(root == null) return paths;
    Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
    Queue<String> pathQueue = new LinkedList<String>();
    nodeQueue.offer(root);
    pathQueue.offer(Integer.toString(root.val));

    while (!nodeQueue.isEmpty()) {
      TreeNode node = nodeQueue.poll(); 
      String path = pathQueue.poll();

      if (node.left == null && node.right == null) {
        paths.add(path);
      } else {
        if (node.left != null) {
          nodeQueue.offer(node.left);
          pathQueue.offer(new StringBuffer(path).append("->").append(node.left.val).toString());
        }

        if (node.right != null) {
          nodeQueue.offer(node.right);
          pathQueue.offer(new StringBuffer(path).append("->").append(node.right.val).toString());
        }
      }
    }
    return paths;
  }
}

执行结果：通过

执行用时：2 ms, 在所有 Java 提交中击败了88.03%的用户
内存消耗：38.9 MB, 在所有 Java 提交中击败了61.93%的用户

复杂度分析：

时间复杂度：O(N²)，其中 N 表示节点数目。分析同方法一。
空间复杂度：O(N²)，其中 N 表示节点数目。在最坏情况下，队列中会存在 N 个节点，保存字符串的队列中每个节点的最大长度为 N，故空间复杂度为 O(N²)