257 Binary Tree Paths

257. Binary Tree Paths

1. Question

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

   1
 /   \
2     3
 \
  5

All root-to-leaf paths are:

["1->2->5", "1->3"]

2. Implementation

(1) DFS

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();        
        getTreePaths(root, "", res);
        return res;
    }

    public void getTreePaths(TreeNode node, String curPath, List<String> res) {
        if (node == null) {
            return;
        }

        if (node.left == null && node.right == null) {
            res.add(curPath + node.val);
            return;
        }

        getTreePaths(node.left, curPath + node.val + "->", res);
        getTreePaths(node.right, curPath + node.val + "->", res);
    }
}

(2) BFS

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

        Queue<TreeNode> queue = new LinkedList<>();
        Queue<String> path = new LinkedList<>();

        queue.add(root);
        path.add("");

        while (!queue.isEmpty()) {
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                TreeNode curNode = queue.remove();
                String curPath = path.remove();

                if (curNode.left == null && curNode.right == null) {
                    res.add(curPath + curNode.val);
                }

                if (curNode.left != null) {
                    queue.add(curNode.left);
                    path.add(curPath + curNode.val + "->");
                }

                if (curNode.right != null) {
                    queue.add(curNode.right);
                    path.add(curPath + curNode.val + "->");
                }
            }
        }
        return res;
    }
}

3. Time & Space Complexity

(1) DFS: 时间复杂度: O(n), 空间复杂度: O(h)

(2) BFS: 时间复杂度: O(n), 空间复杂度: O(w)