Problem

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

Example
Given the following binary tree:

   1
 /   \
2     3
 \
  5
All root-to-leaf paths are:

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

思路一(divide & conquer)

1. get a left child's list and a right child's list
2. prepend root to every string in these two lists
3. put them to root list
4. if root is null , return empty list
5. root does not contains any children, return a list containing itself

    public List<String> binaryTreePaths(TreeNode root) {
        List<String> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        if (root.left == null && root.right == null) {
            list.add(String.valueOf(root.val));
            return list;
        }

        List<String> left = binaryTreePaths(root.left);
        List<String> right = binaryTreePaths(root.right);

        // String s = String.valueOf(root.val);
        StringBuilder sb = new StringBuilder();
        sb.append(root.val);
        for (int i = 0; i < left.size(); i++) {
            int len = sb.length();
            sb.append("->").append(left.get(i));
            list.add(sb.toString());
            sb.setLength(len);
        }

        for (int i = 0; i < right.size(); i++) {
            int len = sb.length();
            sb.append("->").append(right.get(i));
            list.add(sb.toString());
            sb.setLength(len);
        }

        return list;
    }

scala

    def binaryTreePaths(root: TreeNode): List[String] = {
        if (root == null) return List.empty[String]
        if (root.left == null && root.right == null) return List(root.value.toString)
        val leftPaths = binaryTreePaths(root.left)
        val rightPaths = binaryTreePaths(root.right)
        leftPaths.map(p => s"${root.value}->$p") ::: rightPaths.map(p => s"${root.value}->$p")
    }

python

    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        if not root:
            return []
        if not root.left and not root.right:
            return [str(root.val)]

        paths: List[str] = []
        left_paths: List[str] = self.binaryTreePaths(root.left)
        right_paths: List[str] = self.binaryTreePaths(root.right)
        for p in left_paths:
            paths.append(f'{root.val}->{p}')
        for p in right_paths:
            paths.append(f'{root.val}->{p}')
        return paths

思路二(traverse + backtrack)

1. 一个stringbuilder
2. 一个result list, 顺序记录
3. 同等level加一个就要backtrack一次

    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        helper(root, sb, result);
        return result;
    }

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

        int len = sb.length();
        sb.append(root.val);
        sb.append("->");

        helper(root.left, sb, result);
        helper(root.right, sb, result);

        sb.setLength(len);
    }

思路三(traverse)

    def binaryTreePaths(self, root):
        res = []
        def helper(root, p):
            if not root:
                return
            if not root.left and not root.right:
                res.append(p + str(root.val))
                return
            helper(root.left, p + str(root.val) + '->')
            helper(root.right, p + str(root.val) + '->')

        helper(root, "")
        return res