257. Binary Tree Paths

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

Example

Example 1:

Input：{1,2,3,#,5}
Output：["1->2->5","1->3"]
Explanation：
   1
 /   \
2     3
 \
  5

Example 2:

Input：{1,2}
Output：["1->2"]
Explanation：
   1
 /   
2

Method 1:

1. /** 
2.  * Definition for a binary tree node. 
3.  * struct TreeNode { 
4.  *     int val; 
5.  *     TreeNode *left; 
6.  *     TreeNode *right; 
7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {} 
8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} 
9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} 
10.  * }; 
11.  */  
12. class Solution {  
13. public:  
14.     vector<string> binaryTreePaths(TreeNode* root) {  
15.         vector<string> result;  
16.         if (root == NULL) return result;  
17.           
18.         helper(root, to_string(root->val), result);  
19.         return result;  
20.     }  
21.       
22.     void helper(TreeNode* root, string path, vector<string> &result) {  
23.         if (root == NULL) return;  
24.         if (root->left == NULL && root->right == NULL) {  
25.             result.push_back(path);  
26.             return;  
27.         }  
28.           
29.         if (root->left != NULL) {  
30.             helper(root->left, path + "->" + to_string(root->left->val), result);  
31.         }  
32.           
33.         if (root->right != NULL) {  
34.             helper(root->right, path + "->" + to_string(root->right->val), result);  
35.         }  
36.     }  
37. };  

Method 2:

1. /** 
2.  * Definition for a binary tree node. 
3.  * struct TreeNode { 
4.  *     int val; 
5.  *     TreeNode *left; 
6.  *     TreeNode *right; 
7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {} 
8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} 
9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} 
10.  * }; 
11.  */  
12. class Solution {  
13. public:  
14.     /** 
15.      * @param root: the root of the binary tree 
16.      * @return: all root-to-leaf paths 
17.      */  
18.     vector<string> binaryTreePaths(TreeNode * root) {  
19.         vector<string> result;  
20.         if (root == NULL) return result;  
21.           
22.         vector<string> left = binaryTreePaths(root->left);  
23.         vector<string> right = binaryTreePaths(root->right);  
24.           
25.         for (auto l: left) {  
26.             result.push_back(to_string(root->val) + "->" + l);  
27.         }  
28.           
29.         for (auto r: right) {  
30.             result.push_back(to_string(root->val) + "->" + r);  
31.         }  
32.           
33.         if (result.size() == 0) result.push_back(to_string(root->val));  
34.           
35.         return result;  
36.     }  
37. };