Java教程

【学习打卡】第17天 数据结构和算法

本文主要是介绍【学习打卡】第17天 数据结构和算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

路径总和(leetcode - 112)

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

叶子节点 是指没有子节点的节点。

思路一(广度优先遍历)

  1. 创建两个队列A和B,A队列放置节点,B队列放置该节点路径的和
  2. A和B的节点同时出队,如果当前节点为叶子节点,并且和等于targetSum,则直接返回true
  3. 如果不是,则该节点的子节点入队,同时子节点的值加上父节点的和,放入B队列
  4. 循环结束,还没有找出,则返回false
var hasPathSum = function(root, targetSum) {
    if(!root) return false;
    const nodeQueue = [root];
    const sumQueue = [root.val];
    while(nodeQueue.length) {
        const node = nodeQueue.shift();
        const sum = sumQueue.shift();

        if(!node.left && !node.right) {
            if(targetSum === sum) {
                return true
            }
            continue;
        }

        if(node.left) {
            nodeQueue.push(node.left)
            sumQueue.push(node.left.val + sum)
        }
        
        if(node.right) {
            nodeQueue.push(node.right)
            sumQueue.push(node.right.val + sum)
        }
    }
    return false;
};

思路二(深度优先遍历)

  1. 采用递归的方式遍历每个路径下的节点
  2. 每经过一个节点(非叶子节点),使用targetSum 减去该节点的值
  3. 直至叶子节点的值等于相减得到的值,则返回true;否则返回false
var hasPathSum = function(root, targetSum) {
    if(!root) return false

    if(!root.left && !root.right) {
        return targetSum === root.val
    }
    return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val)
};
这篇关于【学习打卡】第17天 数据结构和算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!