代码随想录day18【二叉树】找树左下角的值 路径总和

找树左下角的值

力扣题目

1. 迭代法
2. 递归法
   思路：
   深度最大的时候，第一个结点的值

var findBottomLeftValue = function(root) {
   let maxDepth=0;
   let res=root.val
   var travel=function(root,depth){
       if(!root.left && !root.right){
           if(depth >maxDepth){
               maxDepth =depth
               res = root.val
           }
       }

       if(root.left){
           depth++
           travel(root.left,depth)
           depth--
       }

       if(root.right){
           depth++
           travel(root.right,depth)
           depth--
       }
   }
   travel(root,0)
   return res
};

路径总和

leecode题目
思路：
用递减，让计数器count初始为目标和，然后每次减去遍历路径节点上的数值。如果最后count == 0，同时到了叶子节点的话，说明找到了目标和。
如果遍历到了叶子节点，count不为0，就是没找到。

var hasPathSum = function(root, targetSum) {
    var travel=function(root,targetSum){
        if(!root.left && !root.right){
           return targetSum === 0
       }
       if(root.left){
           if(travel(root.left,targetSum-root.left.val)){//包含回溯
               return true
           }
       }
       if(root.right){
           if( travel(root.right,targetSum-root.right.val)){//包含回溯
               return true
           }
       }
       return false
    }
    if (!root) return false;
    return travel(root,targetSum-root.val)
};

从中序与后序遍历序列构造二叉树(待补充）

力扣题目