257. Binary Tree Paths (Easy)

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"]

Solution 1: BFS O(n); O(w)

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

        Queue<TreeNode> qNode = new LinkedList<>();
        Queue<String> qStr = new LinkedList<>();
        qNode.add(root);
        qStr.add("");
        while (!qNode.isEmpty()) {
            TreeNode curNode = qNode.poll();
            String curStr = qStr.poll();

            if (curNode.left == null && curNode.right == null) { //leaf node
                res.add(curStr + curNode.val);
            }
            if (curNode.left != null) {
                qNode.add(curNode.left);
                qStr.add(curStr + curNode.val + "->");
            }
            if (curNode.right != null) {
                qNode.add(curNode.right);
                qStr.add(curStr + curNode.val + "->");
            }
        }
        return res;
    }

Solution 2: DFS with helper function O(n); O(h)

    /**
     * DFS with helper function O(n);O(h)
     * The path from root to leaf can be obtained by:
     * At each node, add its left child's val to the path, traverse the left subtree.
     * Then add its right child's val to the path, traverse the right subtree.
     * The base case is when we reach a leaf, we add the path to result.
     */
    public List<String> binaryTreePathsC(TreeNode root) {
        List<String> res = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        dfs(root, sb, res);
        return res;
    }

    private void dfs(TreeNode root, StringBuilder sb, List<String> res) {
        if (root == null) {
            return;
        }

        int len = sb.length(); //用sb就多一步backtrack
        sb.append(root.val);
        if (root.left == null && root.right == null) {
            res.add(sb.toString());
            // System.out.println(sb.toString());
        } else {
            sb.append("->");
            dfs(root.left, sb, res);
            dfs(root.right, sb, res);
        }
        sb.setLength(len);
    }

Solution 3: DFS without helper function O(n^2); O(h)

    /**
     * DFS without helper function O(n^2); O(h)
     * Recurrence relation:
     * The paths consist of root + all subtrees paths.
     * Base case:
     * If root == null, the result list would be empty.
     * If root is a leaf node, then its value would be in list.
     */
    public List<String> binaryTreePathsB(TreeNode root) {
        List<String> paths = new ArrayList<>();
        if (root == null) { //exit recursion
            return paths;
        }

        if (root.left == null && root.right == null) {
            paths.add(root.val + "");
            return paths;
        }

        for (String path : binaryTreePathsB(root.left)) { //divide & merge
            paths.add(root.val + "->" + path);
        }
        for (String path : binaryTreePathsB(root.right)) { //divide & merge
            paths.add(root.val + "->" + path);
        }
        return paths;
    }