leetcode Question: Binary Tree Paths

Binary Tree Paths

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

Analysis:

This is a classic depth first search problem.
The idea is

1. Starting from the root node (remember to check NULL)
2. Add current node into path (a string in function parameter) 
3. Check if the current node is a leaf node: if yes, then save path
4. Keep searching the left and right child of current node.

Code(C++):

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void dfs(TreeNode* root, string str, vector<string> &res){
        if (!root){
           return;
        }else{
            if (str == ""){
                str += to_string(root->val);
            }else{
                str = str + "->" + to_string(root->val);    
            }
            if (!root->right && !root->left){
                if (str!=""){
                    res.push_back(str);
                }
            }
            dfs(root->left, str,res);
            dfs(root->right, str,res);
        }
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        string str = "";
        vector<string> res;
        dfs(root,str,res);
        return res;
    }
};

Code(Python):

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def dfs(self, root, s, res):
        if not root:
            return
        else:
            if s == "":
                s += str(root.val)
            else:
                s = s + "->" + str(root.val)
            if not root.right and not root.left:
                if s != "":
                    res.append(s)
            self.dfs(root.right,s,res)
            self.dfs(root.left,s,res)
    
    # @param {TreeNode} root
    # @return {string[]}
    def binaryTreePaths(self, root):
        res = []
        s = ""
        self.dfs(root, s, res)
        return res