一.题目：二叉树的所有路径

二.算法思想

递归版本：

递归终止条件为的结点为空或者为叶子结点，叶子结点的话要把最后一个结点入path后将该path插入vec。

使用类型为vector的vec存储每一条路径path。整个程序像二叉树的前序遍历，但是注意每次左/右递归后要恢复路径（回复到当前结点），所以在递归左/右前设置局部变量path2保存路径。

三.代码

  

   

    

     

    
    

     

      /**
     
    
   

    

     

    
    

     

       * 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<string> vec;
     
    
   

    

     

    
    

     
    //vec作为最终返回的vector值
     
    
   

    

     

    
    

     

          string path;
     
    
   

    

     

    
    

     
    //path字符串表示单条路径
     
    
   

    

     

    
    

     
    vector<string> binaryTreePaths(TreeNode* root) {
     
    
   

    

     

    
    

     
        if(!root){
     
    
   

    

     

    
    

     
            return vec;
     
    
   

    

     

    
    

     

              }//递归终止条件1:结点为空
     
    
   

    

     

    
    

     
        if(!root->left && !root->right){
     
    
   

    

     

    
    

     

                  path+=to_string(root->val);
     
    
   

    

     

    
    

     

                  vec.push_back(path);
     
    
   

    

     

    
    

     
            //完成一条路径的记录
     
    
   

    

     

    
    

     
            return vec;
     
    
   

    

     

    
    

     

              }//递归终止条件2：结点为叶结点
     
    
   

    

     

    
    

     

              path += to_string(root->val) +"->";
     
    
   

    

     

    
    

     

              string path2=path;
     
    
   

    

     

    
    

     
        binaryTreePaths(root->left);
     
    
   

    

     

    
    

     

              path=path2;
     
    
   

    

     

    
    

     
        //恢复path的值，使其去当前结点路径保持一致
     
    
   

    

     

    
    

     
        binaryTreePaths(root->right);
     
    
   

    

     

    
    

     

              path=path2;
     
    
   

    

     

    
    

     
        return vec;
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

      };
     
    
  
 

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/105075435