112.路径总和

LeetCode LeetCode 树深度优先搜索广度优先搜索二叉树

发布时间 : 2000-01-10 01:01

字数:2.4k 阅读 :

112.路径总和

112.路径总和

112.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

112.2 题解

方法一：递归

思路

判断是否存在从根到叶子的路径，使得路径上节点值之和等于 targetSum。可以用递归将问题分解：对于当前节点，检查左右子树是否存在路径和等于 targetSum - 当前节点值。

递归逻辑：

如果当前节点为空，返回 false
如果当前节点是叶子节点（左右子树都为空），判断剩余目标和是否等于当前节点值
递归检查左子树或右子树

举个例子：targetSum = 22

        5
       / \
      4   8
     /   / \
    11  13  4
   / \       \
  7   2       1

递归过程：
- 节点5：检查左子树 targetSum=22-5=17，或右子树 targetSum=17
- 节点4：检查左子树 targetSum=17-4=13
- 节点11：检查左子树 targetSum=13-11=2，或右子树 targetSum=2
- 节点2：是叶子节点，targetSum=2 == 节点值2，返回 true

复杂度分析

时间复杂度：O(n)，最坏情况需要遍历所有节点
空间复杂度：O(h)，递归栈深度为树的高度，最坏情况为 O(n)

代码

// 方法一：递归
// 递归地检查左子树和右子树，将目标和减去当前节点的值传递给子树
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);
}

方法二：使用两个栈并迭代

思路

递归可以用栈来模拟。我们用两个栈：一个存储节点，另一个存储从根到该节点还剩余的目标和。

具体步骤：

将根节点和 targetSum - root.val 入栈
每次从栈中弹出一个节点和对应的剩余目标和
如果该节点是叶子节点且剩余目标和为 0，则找到答案
否则将其子节点和更新后的剩余目标入栈
注意：先压入右子节点再压入左子节点，这样左子节点会先被处理

举个例子：targetSum = 22

        5
       / \
      4   8
     /   / \
    11  13  4
   / \       \
  7   2       1

栈操作：
1. 入栈：(节点5, 剩余17)
2. 出栈：(节点5, 剩余17)，入栈：(节点8, 剩余9), (节点4, 剩余13)
3. 出栈：(节点4, 剩余13)，入栈：(节点11, 剩余2)
4. 出栈：(节点11, 剩余2)，入栈：(节点2, 剩余0), (节点7, 剩余-5)
5. 出栈：(节点2, 剩余0)，是叶子节点且剩余=0，返回 true

复杂度分析

时间复杂度：O(n)，最坏情况需要遍历所有节点
空间复杂度：O(n)，栈中最多存储所有节点

代码

// 方法二：使用两个栈并迭代
// 使用两个栈，一个栈存储节点，另一个栈存储当前节点对应的目标和
// 遍历的把各节点和左右子节点入栈并记录当前节点对应的目标和，当为叶子节点切目标值为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;
}

112.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
}

112.4 运行结果

示例1 方法1 输出：True
示例1 方法2 输出：True
示例2 方法1 输出：False
示例2 方法2 输出：False
示例3 方法1 输出：False
示例3 方法2 输出：False

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