LeetCode112.路径总和

题目

分析

深搜（一）精简

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if(root == NULL) return false;
        if(root->left == NULL && root->right == NULL) 
            return sum-root->val == 0; 
        return hasPathSum(root->left,sum-root->val) || hasPathSum(root->right,sum-root->val);
    }
};

深搜（二）递归函数没有返回值，结果保存在全局变量中 !!!!

 1 class Solution {
 2 public:
 3     bool flag = false;
 4     void dfs(TreeNode*root,int t){
 5         if(root ==NULL ) return;
 6         if(root->left==NULL && root->right==NULL){  //搜索到叶子结点
 7             if(t == 0) {flag = true; return;}
 8         }
 9         if(root->left)  dfs(root->left,t-root->left->val);
10         if(root->right) dfs(root->right,t-root->right->val);
11     }
12     bool hasPathSum(TreeNode* root, int targetSum) {
13         if(root == NULL) return false;
14         dfs(root,targetSum - root->val);
15         return flag;
16     }
17 };

深搜（三）递归函数存在返回值

 1 class Solution {
 2 public:
 3     bool dfs(TreeNode* root,int t){
 4         //搜索到叶子结点
 5         if(!root->left && !root->right && t == 0) return true;
 6         if(!root->left && !root->right && t != 0) return false;
 7         //搜索分支
 8         if(root->left){
 9             if(dfs(root->left,t-root->left->val))  //包含着回溯t-root->left->val
10                 return true;
11         }
12         if(root->right){
13             if(dfs(root->right,t-root->right->val)) //包含着回溯t-root->right->val
14                 return true;
15         } 
16         return false;
17     }
18     bool hasPathSum(TreeNode* root, int targetSum) {
19         if(root == NULL) return false;
20         return dfs(root,targetSum - root->val);
21     }
22 };

广搜,建立两个队列，一个队列保存结点，一个队列保存结点之和

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if(root == NULL) return false;
        queue<TreeNode*>queue1;
        queue<int>queue2;
        queue1.push(root);
        queue2.push(root->val);
        while(!queue1.empty()){
            TreeNode* node = queue1.front();queue1.pop();
            int value = queue2.front();queue2.pop();
            if(node->left == NULL && node->right == NULL){
                if(value == sum) return true;
            }
            if(node->left !=  NULL){queue1.push(node->left);queue2.push(node->left->val + value);}
            if(node->right != NULL){queue1.push(node->right);queue2.push(node->right->val + value);}
            
        }
        return false;
    }
};