129.求根节点到叶节点数字之和

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

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

字数:1.4k 阅读 :

评论:

129.求根节点到叶节点数字之和

129.求根节点到叶节点数字之和

129.1 题目

给你一个二叉树的根节点 root，树中每个节点都存放有一个 0 到 9 之间的数字。每条从根节点到叶节点的路径都代表一个数字：

例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。计算从根节点到叶节点生成的所有数字之和。

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

示例 1：

输入：root = [1,2,3]
输出：25
解释：
从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此，数字总和 = 12 + 13 = 25

示例 2：

输入：root = [4,9,0,5,1]
输出：1026
解释：
从根到叶子节点路径 4->9->5 代表数字 495
从根到叶子节点路径 4->9->1 代表数字 491
从根到叶子节点路径 4->0 代表数字 40
因此，数字总和 = 495 + 491 + 40 = 1026

提示：

树中节点的数目在范围 [1, 1000] 内
0 <= Node.val <= 9
树的深度不超过 10

129.2 题解

深度优先搜索（DFS）

// 方法一：深度优先搜索（DFS）
static int SumNumbers1(TreeNode root)
{
    return DFS(root, 0); // 调用递归函数
}

static int DFS(TreeNode node, int currentSum)
{
    if (node == null) return 0; // 空节点返回0
    currentSum = currentSum * 10 + node.val; // 更新当前路径的数值
    if (node.left == null && node.right == null) return currentSum; // 如果是叶子节点，返回当前路径的数值
    // 递归计算左子树和右子树的路径和
    return DFS(node.left, currentSum) + DFS(node.right, currentSum);
}

广度优先搜索（BFS）

// 方法二：广度优先搜索（BFS）
static int SumNumbers2(TreeNode root)
{
    if (root == null) return 0; // 空树返回0

    int totalSum = 0; // 总和初始化为0
    Queue<(TreeNode node, int currentSum)> queue = new Queue<(TreeNode node, int currentSum)>(); // 创建队列存储节点和当前路径数值
    queue.Enqueue((root, root.val)); // 根节点入队

    // 遍历队列
    while (queue.Count > 0)
    {
        var (node, currentSum) = queue.Dequeue(); // 出队
        
        // 如果是叶子节点，累加当前路径数值
        if (node.left == null && node.right == null)
        {
            totalSum += currentSum; 
        }

        if (node.left != null)
        {
            queue.Enqueue((node.left, currentSum * 10 + node.left.val)); // 左子节点入队
        }

        if (node.right != null)
        {
            queue.Enqueue((node.right, currentSum * 10 + node.right.val)); // 右子节点入队
        }
    }

    return totalSum; // 返回总和
}

129.3 代码

using System;
using System.Collections.Generic;

// 定义树节点类
class TreeNode
{
    public int val; // 节点的值
    public TreeNode left; // 左子节点
    public TreeNode right; // 右子节点

    // 树节点构造函数
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
    {
        this.val = val; // 设置节点值
        this.left = left; // 设置左子节点
        this.right = right; // 设置右子节点
    }
}

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

        // 给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
        // 每条从根节点到叶节点的路径都代表一个数字：
        // 例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
        // 计算从根节点到叶节点生成的 所有数字之和 。
        // 叶节点 是指没有子节点的节点。

        // 示例 1：
        // 输入：root = [1,2,3]
        // 输出：25
        // 解释：
        // 从根到叶子节点路径 1->2 代表数字 12
        // 从根到叶子节点路径 1->3 代表数字 13
        // 因此，数字总和 = 12 + 13 = 25

        // 示例 2：
        // 输入：root = [4,9,0,5,1]
        // 输出：1026
        // 解释：
        // 从根到叶子节点路径 4->9->5 代表数字 495
        // 从根到叶子节点路径 4->9->1 代表数字 491
        // 从根到叶子节点路径 4->0 代表数字 40
        // 因此，数字总和 = 495 + 491 + 40 = 1026

        // 提示：
        // 树中节点的数目在范围 [1, 1000] 内
        // 0 <= Node.val <= 9
        // 树的深度不超过 10

        #endregion

        #region 测试

        // 示例 1
        TreeNode root1 = new TreeNode(1, new TreeNode(2), new TreeNode(3));
        int result1_1 = SumNumbers1(root1);
        Console.WriteLine($"示例1 方法1 输出：{result1_1}");
        int result1_2 = SumNumbers2(root1);
        Console.WriteLine($"示例1 方法2 输出：{result1_2}");

        // 示例 2
        TreeNode root2 = new TreeNode(4, new TreeNode(9, new TreeNode(5), new TreeNode(1)), new TreeNode(0));
        int result2_1 = SumNumbers1(root2);
        Console.WriteLine($"示例2 方法1 输出：{result2_1}");
        int result2_2 = SumNumbers2(root2);
        Console.WriteLine($"示例2 方法2 输出：{result2_2}");

        #endregion
    }

    #region 答案

    // 方法一：深度优先搜索（DFS）
    static int SumNumbers1(TreeNode root)
    {
        return DFS(root, 0); // 调用递归函数
    }

    static int DFS(TreeNode node, int currentSum)
    {
        if (node == null) return 0; // 空节点返回0
        currentSum = currentSum * 10 + node.val; // 更新当前路径的数值
        if (node.left == null && node.right == null) return currentSum; // 如果是叶子节点，返回当前路径的数值
        // 递归计算左子树和右子树的路径和
        return DFS(node.left, currentSum) + DFS(node.right, currentSum);
    }

    // 方法二：广度优先搜索（BFS）
    static int SumNumbers2(TreeNode root)
    {
        if (root == null) return 0; // 空树返回0

        int totalSum = 0; // 总和初始化为0
        Queue<(TreeNode node, int currentSum)> queue = new Queue<(TreeNode node, int currentSum)>(); // 创建队列存储节点和当前路径数值
        queue.Enqueue((root, root.val)); // 根节点入队

        // 遍历队列
        while (queue.Count > 0)
        {
            var (node, currentSum) = queue.Dequeue(); // 出队
            
            // 如果是叶子节点，累加当前路径数值
            if (node.left == null && node.right == null)
            {
                totalSum += currentSum; 
            }

            if (node.left != null)
            {
                queue.Enqueue((node.left, currentSum * 10 + node.left.val)); // 左子节点入队
            }

            if (node.right != null)
            {
                queue.Enqueue((node.right, currentSum * 10 + node.right.val)); // 右子节点入队
            }
        }

        return totalSum; // 返回总和
    }

    #endregion
}

129.4 运行结果

示例1 方法1 输出：25
示例1 方法2 输出：25
示例2 方法1 输出：1026
示例2 方法2 输出：1026

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