首页 > 试题广场 >

二叉树根节点到叶子节点的所有路径和

[编程题]二叉树根节点到叶子节点的所有路径和

热度指数：78312 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个二叉树的根节点root，该树的节点值都在数字 $\ 0-9$ 之间，每一条从根节点到叶子节点的路径都可以用一个数字表示。

1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
2.叶子节点是指没有子节点的节点
3.路径只能从父节点到子节点，不能从子节点到父节点
4.总节点数目为n

例如根节点到叶子节点的一条路径是 $1\to 2\to 3$ ,那么这条路径就用 $\ 123$ 来代替。
找出根节点到叶子节点的所有路径表示的数字之和
例如：

这颗二叉树一共有两条路径，
根节点到叶子节点的路径 $1\to 2$ 用数字 $\ 12$ 代替
根节点到叶子节点的路径 $1\to 3$ 用数字 $\ 13$ 代替
所以答案为 $\ 12+13=25$

数据范围：节点数 $0 \le n \le 100$ ，保证结果在32位整型范围内

要求：空间复杂度 $O(n)$ ，时间复杂度 $O(n^2)$

进阶：空间复杂度 $O(n)$ ，时间复杂度 $O(n)$

示例1

输入

{1,2,3}

输出

示例2

输入

{1,0}

输出

示例3

输入

{1,2,0,3,4}

输出

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

数据结构和算法

发表于 2021-07-19 22:05:15

精华题解 1，DFS解决这题说的是每条从根节点到叶子结点的路径都代表一个数字，然后再把这些数字加起来即可。遍历一棵树从根节点到叶子结点的所有路径，最容易想到的是DFS，所以这题使用DFS是最容易解决的。如果对二叉树的DFS不熟悉的话，可以看下373，数据结构-6,树解决方式就是从根节点往下走的时候，那么展开全文

Maokt

发表于 2021-07-05 14:52:17

精华题解算法思想一：深度优先搜索解题思路：二叉树的每条从根节点到叶子节点的路径都代表一个数字。其实，每个节点都对应一个数字，等于其父节点对应的数字乘以 10 再加上该节点的值（这里假设根节点的父节点对应的数字是 0）。只要计算出每个叶子节点对应的数字，然后计算所有叶子节点对应的路径之和，即可展开全文

Gemini48

发表于 2021-07-08 15:48:17

精华题解分析每条从根到叶子节点的路径都代表一个数字寻找的是符合条件的所有路径之和解法一：深度优先遍历（DFS）思路步骤：每一个结点对应的数字=其父节点对应数字*10加上该结点的值假设根节点的父亲节点对应的数字为0 计算出每一个叶子节点对应的数字计算所有叶子节点对应的数字之和图解展开全文

牛一霸

发表于 2021-07-02 23:55:45

精华题解题目：二叉树根节点到叶子节点的所有路径和描述：给定一个仅包含数字0−9的二叉树，每一条从根节点到叶子节点的路径都可以用一个数字表示。例如根节点到叶子节点的一条路径是1→2→3,那么这条路径就用123来代替。找出根节点到叶子节点的所有路径表示的数字之和例如：这颗二叉树一共有两条路径，根节点展开全文

leaves0924

发表于 2021-07-17 13:58:54

精华题解题目描述给定一个仅包含数字0-9的二叉树，每一条从根节点到叶子节点的路径都可以用一个数字表示。例如根节点到叶子节点的一条路径是 1→2→3,那么这条路径就用 123 来代替。找出根节点到叶子节点的所有路径表示的数字之和例如：这颗二叉树一共有两条路径，根节点到叶子节点的路径 1→2 用数字 12 代展开全文

Peterliang

发表于 2021-07-16 13:27:42

精华题解题意分析这个题目就是要我们找出从根结点到叶子结点的所有的数字，然后我们需要将这些数字拼接成一个数，将所有的数相加起来就是我们的答案了。前置知识，DFS。对于DFS我们可以想象成一棵树，我们需要不断递归到树的最下面的叶子节点。思路分析思路一 DFS 我们对整棵二叉树进行递归操作，同时展开全文

华科不平凡

发表于 2020-08-21 16:16:25

毋庸置疑，用先序遍历。但是实现起来却有点问题。刚开始我用一个string类型变量保存路径上所有数字，用一个int &sum保存结果，但是只通过了95%。后面发现其实可以直接通过一个数字传递路径上数字和，遇到叶节点返回左右子树相加的结果即可。 class Solution { public: 展开全文

下一次什么时候可以修改昵称

发表于 2020-10-29 14:11:07

算法 1.递归 2.重载一个函数sumNumbers(TreeNode root, int sum)表示计算到root节点为止的sum值 3.当左右子节点都为null时，是叶子节点，返回sum 4.当左或右子节点不为null时，不是叶子节点，递归计算左或右子节点的sum值 public int 展开全文