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

 

Credits:

Special thanks to  for adding this problem and creating all test cases.

 

深度优先遍历，每遇到叶节点，将栈中路径记录下来，最后将所有路径转成所需格式

/** * 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:    vector
     
       binaryTreePaths(TreeNode* root) {        vector
      
        path;        if(root == NULL)            return path;        vector
       
        
          > pathv;            unordered_map
         
           visited;        stack
          
            stk; stk.push(root); visited[root] = true; if(root->left == NULL && root->right == NULL) save(pathv, stk); while(!stk.empty()) { TreeNode* top = stk.top(); if(top->left && visited[top->left] == false) { stk.push(top->left); visited[top->left] = true; if(top->left->left == NULL && top->left->right == NULL) save(pathv, stk); continue; } if(top->right && visited[top->right] == false) { stk.push(top->right); visited[top->right] = true; if(top->right->left == NULL && top->right->right == NULL) save(pathv, stk); continue; } stk.pop(); } return convert(pathv); } void save(vector
           
            
              >& pathv, stack
             
               stk) { vector
              
                cur; while(!stk.empty()) { TreeNode* top = stk.top(); cur.push_back(top->val); stk.pop(); } reverse(cur.begin(), cur.end()); pathv.push_back(cur); } vector
               
                 convert(vector
                
                 
                   >& pathv) { vector
                  
                    path; for(int i = 0; i < pathv.size(); i ++) { string cur; cur += to_string(pathv[i][0]); for(int j = 1; j < pathv[i].size(); j ++) { cur += "->"; cur += to_string(pathv[i][j]); } path.push_back(cur); } return path; }};