257. Binary Tree Paths

Link

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

Note: A leaf is a node with no children.

Example:

Input:

   1
 /   \
2     3
 \
  5

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

Explanation: All root-to-leaf paths are: 1->2->5, 1->3

Solution

這題有點Backtracking的影子，就是列舉所有可能。當有左子樹時往左走查找左子樹的所有可能path，若有右子樹時多查找右子樹的所有path。

T: O(N) , n 是樹內元素個數，基本上就是travel all the element to find the path to leaf

   public List<String> binaryTreePaths(TreeNode root) {
        List<String> ret = new ArrayList<>();
        if(root == null) return ret;
        helper(root, "", ret);
        return ret;
    }
    
    public void helper(TreeNode node, String temp, List<String> finalRet){
        
        if(node.left == null && node.right == null){
            temp += node.val;
            finalRet.add(temp);
        }
        if(node.left != null){
            helper(node.left, temp + node.val + "->", finalRet);
        }
        if(node.right != null){
            helper(node.right, temp + node.val + "->", finalRet);
        }
        
    }