leetcode系列--112. 路径总和

leetcode系列–第112题.路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。
判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。

//js 树结构
var root = {
   val: 5,
   left: {
       val: 4,
       left: {
           val: 11,
           left: {
               val: 7,
               left: null,
               right: null
           },
           right: {
               val: 2,
               left: null,
               right: null
           }
       },
       right: null
   },
   right: {
       val: 8,
       left: {
           val: 13,
           left: null,
           right: null
       },
       right: {
           val: 4,
           left: null,
           right: {
               val: 1,
               left: null,
               right: null
           }
       }
   }
}

// DFS (深度优先遍历) 递归
var hasPathSum = function (root, targetSum) {
    // 递归首先确定结束条件
    if (root === null) {
        return false
    }
    // 根据题意需要判断叶子节点
    if (root.left === null && root.right === null && targetSum - root.val === 0) 	{
        return true
    }
    // 否则递归
    return hasPathSum1(root.left, targetSum - root.val) 
    || hasPathSum1(root.right, targetSum - root.val)
}

// DFS (深度优先遍历) 迭代
var hasPathSum = function (root, targetSum) {
    const stack = [[root, targetSum - root.val]]; // 初始栈
    if (root === null) {
        return false
    }
    while (stack.length > 0) {
        // 出栈
        const pop = stack.pop()
        let node = pop[0]
        let remain = pop[1]
        // 叶子结点
        if (node.left === null && node.right === null && remain === 0) {
            return true
        }
        if (node.right) {
            stack.push([node.right, remain - node.right.val])
        }
        if (node.left) {
            stack.push([node.left, remain - node.left.val])
        }
    }
    return false
}

var hasPathSum = function (root, targetSum) {
    // BFS (广度优先遍历) 迭代
    if (root === null) {
        return false
    }
    // 创建两个数组
    // 一个数组记录所有的节点 一个记录路径和
    const queue = []
    const res = []
    // 初始化
    queue.push(root)
    res.push(root.val)

    // 进入广度优先遍历
    while (queue.length > 0) {
        const top = queue.pop()
        const temp = res.pop()

        // 叶子结点
        if (top.left === null && top.right === null && targetSum - temp === 0) {
            return true
        }
        if (top.left) {
            queue.push(top.left)
            res.push(temp + top.left.val)
        }
        if (top.right) {
            queue.push(top.right)
            res.push(temp + top.right.val)
        }
    }
    return false
}