问题

给出一棵二叉树及一个和值，检查该树是否存在一条根到叶子的路径，该路径经过的所有节点值的和等于给出的和值。

例如，

给出以下二叉树及和值22:

         5

        / \

       4  8

      /   / \

    11 13 4

    / \        \

  7   2        1

函数返回true，因为存在一条根到叶子的路径5->4->11->2，其路径和为22。

 

初始思路

鉴于题目要求找到一条路径和符合要求即可，选择层次遍历二叉树是一种比较合适的选择－保证了我们首先找到的是最短的路径从而节省了时间。另外由于没有禁止修改原二叉树的值，我们在处理过程中可以把每个点的值修改为到达这点时的路径和，方便比较。至于层次遍历的方法，大家应该已经很熟悉了，使用中的双vector法即可：

1 class Solution { 2     public: 3         bool hasPathSum(TreeNode *root, int sum) 4         { 5             if(!root) 6             { 7                 return false; 8             } 9             10             treeLevel_[0].clear();11             treeLevel_[1].clear();12             13             bool flag = false;14             treeLevel_[0].push_back(root);15             16             while(!treeLevel_[flag].empty())17             {18                 for(auto iter = treeLevel_[flag].begin(); iter != treeLevel_[flag].end(); ++iter)19                 {20                     if(!(*iter)->left && !(*iter)->right)21                     {22                         if((*iter)->val == sum)23                         {24                             return true;25                         }26                     }27                     28                     if((*iter)->left)29                     {30                         (*iter)->left->val += (*iter)->val;31                         32                         treeLevel_[!flag].push_back((*iter)->left);33                     }34                     35                     if((*iter)->right)36                     {37                         (*iter)->right->val += (*iter)->val;38 39                         40                         treeLevel_[!flag].push_back((*iter)->right);41                     }42                 }43                 44                 treeLevel_[flag].clear();45                 46                 flag = !flag;47             }48             49             return false;50         }51         52     private:53         54         std::vector
      
        treeLevel_[2];55     };
      

提交后Judge Small和Judge Large双双通过。

 

扩展问题

给出一棵二叉树及一个和值，找出符合条件的所有根到叶子的路径，这些路径经过的所有节点值的和等于给出的和值。

例如，

给出以下二叉树及和值22:

         5 

        / \

       4  8

      /   / \

    11 13 4

    / \     / \

  7   2  5    1

返回

[

  [5,4,11,2],

  [5,8,4,5]

]

 

扩展问题初始思路

题目要求找出所有符合条件的路径，意味着不管用什么方法都必须把所有节点遍历一遍。如果还是使用前面的层次遍历，因为是广度优先遍历，需要同时跟踪多条路径的和，直到走到叶子节点。因此在这里我们尝试使用普通的递归中序遍历，由于这是一种深度优先遍历，通过进栈及出栈操作，可以做到一次只需跟踪一条路径即可：

1 class Solution113 { 2     public: 3         std::vector
      
       
         > pathSum(TreeNode *root, int sum) 4         { 5             result_.clear(); 6             if(!root) 7             { 8                 return result_; 9             }10             11             currentPath_.clear();12             currentPath_.push_back(root->val);13             sum_ = sum;14             currentSum_ = root->val;15             16             FindPathSum(root);17             18             return result_;19         }20         21     private:22         23         void FindPathSum(TreeNode *node)24         {25             if(!node->left && !node->right)26             {27                 if(currentSum_ == sum_)28                 {29                     result_.push_back(currentPath_);30                 }31                 32                 return;33             }34             35             if(node->left)36             {37                 currentSum_ += node->left->val;38                 currentPath_.push_back(node->left->val);39                 FindPathSum(node->left);40                 currentSum_ -= node->left->val;41                 currentPath_.pop_back();42             }43             44             if(node->right)45             {46                 currentSum_ += node->right->val;47                 currentPath_.push_back(node->right->val);48                 FindPathSum(node->right);49                 currentSum_ -= node->right->val;50                 currentPath_.pop_back();51             }52             53         }54         55         std::vector
        
         
           > result_;56         std::vector
          
            currentPath_;57         int sum_;58         int currentSum_;59         60     };
          
         
        
       
      

提交后同样Judge Small和Judge Large双双通过。