leetcode112：路径总和 #45

Activity

1. sisterAn

   added

   LeetCode

   字节

   on May 19, 2020
2. 7777sea commented on May 20, 2020

   

   7777sea

   on May 20, 2020

   More actions

   var hasPathSum = function(root, sum) {
        
     if (root === null) return false
     if (root.left === null && root.right === null && root.val === sum) return true
     return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val)
   
   };
   
3. Malenconiaprincep commented on May 20, 2020

   

   Malenconiaprincep

   on May 20, 2020

   Last edited by Malenconiaprincep

   More actions

   深度遍历

   var hasPathSum = function(root, sum) {
       return dfs(root,sum)
   };
   
   var dfs = function(root, sum) {
       if(root === null) return false
       if(!root.left && !root.right && root.val === sum) return true
       return dfs(root.left, sum - root.val) || dfs(root.right, sum - root.val)
   }
   
4. plane-hjh commented on May 20, 2020

   

   plane-hjh

   on May 20, 2020

   More actions

   深度优先遍历

   /**
    * Definition for a binary tree node.
    * function TreeNode(val) {
    *     this.val = val;
    *     this.left = this.right = null;
    * }
    */
   /**
    * @param {TreeNode} root
    * @param {number} sum
    * @return {boolean}
    */
   var hasPathSum = function(root, sum) {
     // 根节点为空
     if (root === null) return false;
   
     // 只有一个根节点，主要是这里的两个判断
     if (root.left === null && root.right === null && root.val === sum) return true;
   
     // 把总和减去当前值递归下去
     const left = hasPathSum(root.left, sum - root.val);
     const right = hasPathSum(root.right, sum - root.val);
     return left || right;
   };

   迭代

   /**
    * Definition for a binary tree node.
    * function TreeNode(val) {
    *     this.val = val;
    *     this.left = this.right = null;
    * }
    */
   /**
    * @param {TreeNode} root
    * @param {number} sum
    * @return {boolean}
    */
   var hasPathSum = function(root, sum) {
     if (root === null) return false;
     let stack = [root];
     let sumStack = [sum - root.val];
     while (stack.length > 0) {
       let node = stack.pop();
       let curSum = sumStack.pop();
       if (node.left === null && node.right === null && curSum === 0) {
         return true;
       }
       if (node.right !== null) {
         stack.push(node.right);
         sumStack.push(curSum - node.right.val);
       }
       if (node.left !== null) {
         stack.push(node.left);
         sumStack.push(curSum - node.left.val);
       }
     }
     return false;
   };

   这些都是二叉树遍历的延伸问题
5. sisterAn commented on May 20, 2020

   

   sisterAn

   on May 20, 2020

   OwnerAuthor

   More actions

   解题思路：

   只需要遍历整棵树

   • 如果当前节点不是叶子节点，递归它的所有子节点，传递的参数就是 sum 减去当前的节点值；
   • 如果当前节点是叶子节点，判断参数 sum 是否等于当前节点值，如果相等就返回 true，否则返回 false。

   代码实现：

   var hasPathSum = function(root, sum) {
     // 根节点为空
     if (root === null) return false;
     
     // 叶节点 同时 sum 参数等于叶节点值
     if (root.left === null && root.right === null) return root.val === sum;
   
     // 总和减去当前值，并递归
     sum = sum - root.val
     return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
   };

   leetcode

   👍React with 👍2Reacted by xingyu and Stephan_zhang
6. GolderBrother commented on May 27, 2020

   

   GolderBrother

   on May 27, 2020

   More actions

   • 如果根节点为空，直接返回 false
   • 如果左节点和右节点都为空，就直接比较根节点值
   • 将总和减去当前值得到差值，不断递归来找是否等于这个差值的值，左节点找不到就找右节点

   /**
    * @param {TreeNode} root
    * @param {number} sum
    * @return {boolean}
    */
   var hasPathSum = function(root, sum) {
     // 根节点为空，直接返回false
     if (root == null) return false;
     // 左节点和右节点都为空，就直接比较根接点值
     if (root.left == null && root.right == null) return root.val === sum;
     // 将总和减去当前值得到差值，不断递归来找是否等于这个差值的值，左节点找不到就找右节点
     sum = sum - root.val;
     return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
   };
7. AnranS commented on Nov 20, 2020

   

   AnranS

   on Nov 20, 2020

   More actions

   var hasPathSum = function(root, sum) {
       let numSum = 0;
       let res = false;
       function help(root) {
           if(!root) return;
           numSum+=root.val;
           help(root.left);
           help(root.right);
           // 走到根节点
           if(!root.left&&!root.right) {
               if(numSum === sum){
                   res = true;
               }
           }
           numSum-=root.val;
       }
       help(root);
       return res;
   };