面试算法49:从根节点到叶节点的路径数字之和

这篇具有很好参考价值的文章主要介绍了面试算法49:从根节点到叶节点的路径数字之和。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目

在一棵二叉树中所有节点都在0~9的范围之内,从根节点到叶节点的路径表示一个数字。求二叉树中所有路径表示的数字之和。例如,图8.4的二叉树有3条从根节点到叶节点的路径,它们分别表示数字395、391和302,这3个数字之和是1088。
面试算法49:从根节点到叶节点的路径数字之和,算法,算法,面试,职场和发展

分析

首先考虑如何计算路径表示的数字。顺着指向子节点的指针路径向下遍历二叉树,每到达一个节点,相当于在路径表示的数字末尾添加一位数字。例如,在最开始到达根节点时,它表示数字3。然后到达节点9,此时路径表示数字39(3×10+9=39)。然后向下到达节点5,此时路径表示数字395(39×10+5=395)。

这就是说,每当遍历到一个节点时都计算从根节点到当前节点的路径表示的数字。如果这个节点还有子节点,就把这个值传下去继续遍历它的子节点。先计算到当前节点为止的路径表示的数字,再计算到它的子节点的路径表示的数字,这实质上就是典型的二叉树前序遍历。文章来源地址https://www.toymoban.com/news/detail-740790.html

public class Test {
    public static void main(String[] args) {
        TreeNode node3 = new TreeNode(3);
        TreeNode node9 = new TreeNode(9);
        TreeNode node0 = new TreeNode(0);
        TreeNode node5 = new TreeNode(5);
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);

        node3.left = node9;
        node3.right = node0;
        node9.left = node5;
        node9.right = node1;
        node0.right = node2;

        int result = sumNumbers(node3);
        System.out.println(result);
    }

    public static int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }

    private static int dfs(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }

        sum = sum * 10 + root.val;
        if (root.left == null && root.right == null) {
            return sum;
        }

        return dfs(root.left, sum) + dfs(root.right, sum);
    }
}

到了这里,关于面试算法49:从根节点到叶节点的路径数字之和的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LeetCode_二叉树_DFS_中等_129.求根节点到叶节点数字之和

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

    2024年02月08日
    浏览(41)
  • 每日OJ题_二叉树dfs②_力扣129. 求根节点到叶节点数字之和

    目录 力扣129. 求根节点到叶节点数字之和 解析代码 129. 求根节点到叶节点数字之和 难度 中等 给你一个二叉树的根节点  root  ,树中每个节点都存放有一个  0  到  9  之间的数字。 每条从根节点到叶节点的路径都代表一个数字: 例如,从根节点到叶节点的路径  1 - 2 - 3

    2024年02月21日
    浏览(44)
  • DFS | 从根到叶的二进制数之和【附递归展开图】

    👉 力扣原题链接 首先我们来分析一下本题的思路 题目说到要求解每一条路径上的结点数字之和,但是本题并不是就简单的累加,而是要结合二进制的知识 对于每一条从根到叶的路径都代表一个从最高有效位开始的二进制数,要注意的是这个 最高有效位 ,也就是说越往下走

    2023年04月08日
    浏览(81)
  • [力扣 129]求根节点到叶节点之和

    题目描述: 思路: 可以采用递归+回溯。递归访问左-右-根节点并记录路径。到叶节点后,计算数字并相加。 代码:

    2024年04月14日
    浏览(30)
  • 面试算法100:三角形中最小路径之和

    在一个由数字组成的三角形中,第1行有1个数字,第2行有2个数字,以此类推,第n行有n个数字。例如,下图是一个包含4行数字的三角形。如果每步只能前往下一行中相邻的数字,请计算从三角形顶部到底部的路径经过的数字之和的最小值。从三角形顶部到底部的路径数字之和

    2024年01月16日
    浏览(44)
  • ​LeetCode解法汇总1080. 根到叶路径上的不足节点

    https://github.com/September26/java-algorithms 给你二叉树的根节点  root  和一个整数  limit  ,请你同时删除树中所有  不足节点  ,并返回最终二叉树的根节点。 假如通过节点  node  的每种可能的 “根-叶” 路径上值的总和全都小于给定的  limit ,则该节点被称之为  不足节点 

    2024年02月06日
    浏览(36)
  • 从根到叶:深度理解哈希表

    关于查找元素时: 在顺序结构以及平衡树 中,元素关键码与其存储位置之间没有对应的关系,因此在 查找一个元素时,必须要经过关键 码的多次比较 。 顺序查找时间复杂度为 O(N) ,平衡树中为树的高度,即 O( log2 N ) ,搜索的效率取决于搜索过程中元素的比较次数。 理想

    2024年03月19日
    浏览(67)
  • 代码随想录额外题目| 二叉树 ●129求根到叶数字之和 ●1382二叉树变平衡●100相同的树

    #129求根到叶数字之和 回溯放进vector,然后从后往前拿,乘1 10 100 ... 很基础的回溯 my code: 随想录跟我思路差不多,但这两个是放globa的:int result; vectorint path; 最近总觉得global不安全不想放  #1382二叉树变平衡 本来遇到这种会换root的就头疼,然后看了眼随想录,是要先变成

    2024年02月14日
    浏览(34)
  • Leetcode129. 求根到叶子节点数字之和

    力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 给你一个二叉树的根节点  root  ,树中每个节点都存放有一个  0  到  9  之间的数字。 每条从根节点到叶节点的路径都代表一个数字: 例如,从根节点到叶子节点的路径  1 - 2 - 3  表示数字  123  。 计算从根节点到叶节

    2024年02月09日
    浏览(38)
  • Brandes算法计算无向图节点最短路径之和-Java代码实现

            Brandes算法是一种经典的计算中介中心性的算法,它通过计算节点对之间的最短路径数量来评估节点的中介中心性。在复杂网络分析中,中介中心性是一种常用的指标,用于衡量节点在网络中的重要性程度。中介中心性越高的节点往往具有更大的影响力,可能成为

    2024年04月23日
    浏览(30)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包