0257.md

257. Binary Tree Paths

Level:

Topic:

Question

Given the root of a binary tree, return all root-to-leaf paths in any order.

Input: root = [1,2,3,null,5]
Output: ["1->2->5","1->3"]

Intuition

Recursive:

• since right subtree will inherit the previous established path, use a new stringbuilder to add so it would memorize.

Backtrack:

• after traversing children, remove the last inserted node val

Code

Time: O(n)
Space: O(n)

Recursive

List<String> ans = new ArrayList<>();
public List<String> binaryTreePaths(TreeNode root) {
    findPath(root, new StringBuilder());
    return ans;
}

private void findPath(TreeNode root, StringBuilder s) {
    if (root == null)
        return;

    StringBuilder sb = new StringBuilder(s);
    sb.append(root.val);
    if (root.left == null && root.right == null) {
        ans.add(sb.toString());
        return;
    }
    sb.append("->");
    findPath(root.left, sb);
    findPath(root.right, sb);
}