LeetCode C++ 129. Sum Root to Leaf Numbers【Tree/DFS】中等
发布日期:2021-07-01 02:52:57
浏览次数:2
分类:技术文章
本文共 2540 字,大约阅读时间需要 8 分钟。
Given a binary tree containing digits from 0-9
only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3
which represents the number 123
. Find the total sum of all root-to-leaf numbers.
Note: A leaf is a node with no children.
Example:
Input: [1,2,3] 1 / \ 2 3Output: 25Explanation:The root-to-leaf path 1->2 represents the number 12.The root-to-leaf path 1->3 represents the number 13.Therefore, sum = 12 + 13 = 25.
Example 2:
Input: [4,9,0,5,1] 4 / \ 9 0 / \5 1Output: 1026Explanation:The root-to-leaf path 4->9->5 represents the number 495.The root-to-leaf path 4->9->1 represents the number 491.The root-to-leaf path 4->0 represents the number 40.Therefore, sum = 495 + 491 + 40 = 1026.
题意:给定一个二叉树,它的每个结点都存放一个 0-9
的数字,每条从根到叶子节点的路径都代表一个数字。例如,从根到叶子节点路径 1->2->3
代表数字 123
。计算从根到叶子节点生成的所有数字之和。
思路1 递归先序搜索
先序遍历,计算和即可。代码如下:
class Solution { public: int getAllNumbers(TreeNode* root, int num) { if (!root) return 0; if (!root->left && !root->right) return num * 10 + root->val; int val = num * 10 + root->val; return getAllNumbers(root->left, val) + getAllNumbers(root->right, val); } int sumNumbers(TreeNode* root) { return getAllNumbers(root, 0); }};
效率如下:
执行用时:0 ms, 在所有 C++ 提交中击败了100.00% 的用户内存消耗:12.2 MB, 在所有 C++ 提交中击败了34.94% 的用户
20201029 Update 如果使用原函数的话,可以写成如下形式:
class Solution { public: int sum = 0, num = 0; int sumNumbers(TreeNode* root) { if (root == nullptr) return 0; num = num * 10 + root->val; if (root->left == nullptr && root->right == nullptr) sum += num; sumNumbers(root->left); sumNumbers(root->right); num /= 10; //回溯到上一层 return sum; }};
效率不是很好:
执行用时:8 ms, 在所有 C++ 提交中击败了35.13% 的用户内存消耗:12.4 MB, 在所有 C++ 提交中击败了28.99% 的用户
思路2 非递归先序遍历
实际代码如下:
class Solution { public: int sumNumbers(TreeNode* root) { stackst; int sum = 0; TreeNode *temp = root; while (temp || !st.empty()) { while (temp) { st.push(temp); if (temp->left) temp->left->val += temp->val * 10; //修改原树上的值 temp = temp->left; } temp = st.top(); st.pop(); if (!temp->left && !temp->right) sum += temp->val; //遇到叶子节点 if (temp->right) temp->right->val += temp->val * 10; //修改原树上的值 temp = temp->right; } return sum; }};
效率如下:
执行用时:8 ms, 在所有 C++ 提交中击败了34.87% 的用户内存消耗:12.2 MB, 在所有 C++ 提交中击败了36.07% 的用户
转载地址:https://memcpy0.blog.csdn.net/article/details/108923555 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
留言是一种美德,欢迎回访!
[***.207.175.100]2024年04月21日 11时48分11秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
架构师进阶必看!架构师的工作都干些什么?
2019-05-02
详解RDMA架构和技术原理
2019-05-02
Virtio技术架构简明分析
2019-05-02
浅谈数据库高可用性(HA)技术
2019-05-02
许式伟的架构课
2019-05-02
Linux调试工具
2019-05-02
用Eclipse和GDB构建ARM交叉编译和在线调试环境
2019-05-02
cfs 完全公平调度
2019-05-02
如何判断自己是否具有成为一名优秀程序员的潜质
2019-05-02
创业公司和求职者都应看的九个面试题
2019-05-02
内核的链接脚本文件vmlinux.lds.S
2019-05-02
Ubuntu下 rsync同步文件实例
2019-05-02
安装Samba时遇到错误
2019-05-02
Linux Shell编程入门
2019-05-02
EMACS利用etags查阅大型工程代码
2019-05-02
C++名稱空間(Namespace)的介绍
2019-05-02
通过源码查看Android 版本
2019-05-02
getopts命令详解
2019-05-02
Java接口详解
2019-05-02