题解 | #二叉树中和为某一值的路径(一)#

/**

• struct TreeNode {
• int val;
• struct TreeNode *left;
• struct TreeNode *right;
• }; */

本题的解题思路是先用队列层次遍历一边树，再将树的VAL值改成权值（从根节点出发的值），更改完之后再用队列再从新遍历一边节点，找到sum值于权值相同的节点，同时判断它是不是叶子节点。这里用到了两个队列，有大佬用一个栈就实现了，不过内存是一样的，理论上用栈可能更***觉代码有很多冗余的地方，有空我再来修改

class Solution { public: /** * * @param root TreeNode类 * @param sum int整型 * @return bool布尔型 / bool hasPathSum(TreeNode root, int sum) { // write code here if(!root) return false;//判断树是不是空的 queue<TreeNode *>q; if((root->val==sum)&&(root->left==NULL)&&(root->right==NULL)) return true;//判断树是不是只有一个节点且权值为空

    q.push(root);

// if((root->left==NULL)&&(root->right==NULL)) // return false;

    while(!q.empty()){ //遍历树加权值
        TreeNode *n1=q.front();
        q.pop();
        int a=n1->val;
        
        if(n1->left){
             n1->left->val=n1->left->val+a; 
         q.push(n1->left);
          
        }
         if(n1->right){
             n1->right->val=n1->right->val+a;  
         q.push(n1->right);
          
        }
    }
    q.push(root);
    while(!q.empty()){ //查找权值等于SUM的节点
        TreeNode *n1=q.front();
        q.pop();
        
        if(n1->left){
         q.push(n1->left);
          
        }
         if(n1->right){
         q.push(n1->right);
        }
        if((n1->val==sum)&&(n1->left==NULL)&&(n1->right==NULL))
            return true;
    }
      return false;
}

};