112.路径总和

LeetCode LeetCode 树 深度优先搜索 广度优先搜索 二叉树
发布时间 :
字数:1.8k 阅读 : 评论:
  1. 112.路径总和
    1. 12.1 题目
    2. 12.2 题解
      1. 递归
      2. 使用两个栈并迭代
    3. 12.3 代码
    4. 12.4 运行结果

112.路径总和

12.1 题目

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

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

示例 1：

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

示例 2：

输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 –> 2): 和为 3
(1 –> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。

示例 3：

输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。

提示：

  • 树中节点的数目在范围 [0, 5000] 内
  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000

12.2 题解

递归

// 方法一：递归
// 递归地检查左子树和右子树，将目标和减去当前节点的值传递给子树
static bool HasPathSum1(TreeNode root, int targetSum)
{
    // 如果当前节点为空，返回 false
    if (root == null)
        return false;

    // 如果当前节点是叶子节点，并且目标和等于当前节点的值，返回 true
    if (root.left == null && root.right == null && targetSum == root.val)
        return true;

    // 递归检查左子树和右子树
    return HasPathSum1(root.left, targetSum - root.val) || HasPathSum1(root.right, targetSum - root.val);
}

使用两个栈并迭代

// 方法二：使用两个栈并迭代
// 使用两个栈，一个栈存储节点，另一个栈存储当前节点对应的目标和
// 遍历的把各节点和左右子节点入栈并记录当前节点对应的目标和，当为叶子节点切目标值为0是则代表找到
static bool HasPathSum2(TreeNode root, int targetSum)
{
    // 如果根节点为空，返回 false
    if (root == null)
        return false;

    // 创建两个栈，一个用于存储节点，另一个用于存储当前节点对应的目标和
    Stack<TreeNode> nodeStack = new Stack<TreeNode>();
    Stack<int> sumStack = new Stack<int>();

    // 将根节点和对应的目标和入栈
    nodeStack.Push(root);
    sumStack.Push(targetSum - root.val);

    // 循环直到栈为空
    while (nodeStack.Count > 0)
    {
        // 弹出栈顶的节点和对应的目标和
        TreeNode currentNode = nodeStack.Pop();
        int currentSum = sumStack.Pop();

        // 如果当前节点是叶子节点，并且目标和等于当前节点的值，返回 true
        if (currentNode.left == null && currentNode.right == null && currentSum == 0)
            return true;

        // 将当前节点的右子节点和对应的目标和入栈
        if (currentNode.right != null)
        {
            nodeStack.Push(currentNode.right);
            sumStack.Push(currentSum - currentNode.right.val);
        }

        // 将当前节点的左子节点和对应的目标和入栈
        if (currentNode.left != null)
        {
            nodeStack.Push(currentNode.left);
            sumStack.Push(currentSum - currentNode.left.val);
        }
    }

    // 若循环结束仍未找到满足条件的路径，返回 false
    return false;
}

12.3 代码

using System;
using System.Collections.Generic;

class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int x)
    {
        val = x;
    }
}

class Program
{
    static void Main()
    {
        #region 题目

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

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

        // 示例 2：
        // 输入：root = [1,2,3], targetSum = 5
        // 输出：false
        // 解释：树中存在两条根节点到叶子节点的路径：
        // (1 --> 2): 和为 3
        // (1 --> 3): 和为 4
        // 不存在 sum = 5 的根节点到叶子节点的路径。

        // 示例 3：
        // 输入：root = [], targetSum = 0
        // 输出：false
        // 解释：由于树是空的，所以不存在根节点到叶子节点的路径。

        // 提示：
        // 树中节点的数目在范围 [0, 5000] 内
        // -1000 <= Node.val <= 1000
        // -1000 <= targetSum <= 1000

        #endregion

        #region 测试

        // 示例 1
        TreeNode root1 = new TreeNode(5)
        {
            left = new TreeNode(4)
            {
                left = new TreeNode(11)
                {
                    left = new TreeNode(7),
                    right = new TreeNode(2)
                }
            },
            right = new TreeNode(8)
            {
                left = new TreeNode(13),
                right = new TreeNode(4)
                {
                    right = new TreeNode(1)
                }
            }
        };
        int targetSum1 = 22;
        bool result1 = HasPathSum1(root1, targetSum1);
        Console.WriteLine($"示例1 方法1 输出：{result1}");
        bool result1_2 = HasPathSum2(root1, targetSum1);
        Console.WriteLine($"示例1 方法2 输出：{result1_2}");

        // 示例 2
        TreeNode root2 = new TreeNode(1)
        {
            left = new TreeNode(2),
            right = new TreeNode(3)
        };
        int targetSum2 = 5;
        bool result2 = HasPathSum1(root2, targetSum2);
        Console.WriteLine($"示例2 方法1 输出：{result2}");
        bool result2_2 = HasPathSum2(root2, targetSum2);
        Console.WriteLine($"示例2 方法2 输出：{result2_2}");

        // 示例 3
        TreeNode root3 = null;
        int targetSum3 = 0;
        bool result3 = HasPathSum1(root3, targetSum3);
        Console.WriteLine($"示例3 方法1 输出：{result3}");
        bool result3_2 = HasPathSum2(root3, targetSum3);
        Console.WriteLine($"示例3 方法2 输出：{result3_2}");

        #endregion
    }

    #region 答案

    // 方法一：递归
    // 递归地检查左子树和右子树，将目标和减去当前节点的值传递给子树
    static bool HasPathSum1(TreeNode root, int targetSum)
    {
        // 如果当前节点为空，返回 false
        if (root == null)
            return false;

        // 如果当前节点是叶子节点，并且目标和等于当前节点的值，返回 true
        if (root.left == null && root.right == null && targetSum == root.val)
            return true;

        // 递归检查左子树和右子树
        return HasPathSum1(root.left, targetSum - root.val) || HasPathSum1(root.right, targetSum - root.val);
    }

    // 方法二：使用两个栈并迭代
    // 使用两个栈，一个栈存储节点，另一个栈存储当前节点对应的目标和
    // 遍历的把各节点和左右子节点入栈并记录当前节点对应的目标和，当为叶子节点切目标值为0是则代表找到
    static bool HasPathSum2(TreeNode root, int targetSum)
    {
        // 如果根节点为空，返回 false
        if (root == null)
            return false;

        // 创建两个栈，一个用于存储节点，另一个用于存储当前节点对应的目标和
        Stack<TreeNode> nodeStack = new Stack<TreeNode>();
        Stack<int> sumStack = new Stack<int>();

        // 将根节点和对应的目标和入栈
        nodeStack.Push(root);
        sumStack.Push(targetSum - root.val);

        // 循环直到栈为空
        while (nodeStack.Count > 0)
        {
            // 弹出栈顶的节点和对应的目标和
            TreeNode currentNode = nodeStack.Pop();
            int currentSum = sumStack.Pop();

            // 如果当前节点是叶子节点，并且目标和等于当前节点的值，返回 true
            if (currentNode.left == null && currentNode.right == null && currentSum == 0)
                return true;

            // 将当前节点的右子节点和对应的目标和入栈
            if (currentNode.right != null)
            {
                nodeStack.Push(currentNode.right);
                sumStack.Push(currentSum - currentNode.right.val);
            }

            // 将当前节点的左子节点和对应的目标和入栈
            if (currentNode.left != null)
            {
                nodeStack.Push(currentNode.left);
                sumStack.Push(currentSum - currentNode.left.val);
            }
        }

        // 若循环结束仍未找到满足条件的路径，返回 false
        return false;
    }



    #endregion
}

12.4 运行结果

示例1 方法1 输出：True
示例1 方法2 输出：True
示例2 方法1 输出：False
示例2 方法2 输出：False
示例3 方法1 输出：False
示例3 方法2 输出：False
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2024 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏