[C++]LeetCode404. 左叶子之和
2021/11/24 14:10:48
本文主要是介绍[C++]LeetCode404. 左叶子之和,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
404. 左叶子之和
当遇到左叶子节点的时候,记录数值,然后通过递归求取左子树左叶子之和,和 右子树左叶子之和,相加便是整个树的左叶子之和。
深度优先搜索
class Solution { public: int sumOfLeftLeaves(TreeNode* root) { if(root == NULL) return 0; //递归求左子树的左叶子节点 int leaftvalue = sumOfLeftLeaves(root->left); //递归求右子树的左叶子节点 int rightvalue = sumOfLeftLeaves(root->right); int midvalue = 0; //左叶子节点不为空,且左叶子节点的左右子节点为空,则记录当前左叶子节点的值 if(root->left && !root->left->left && !root->left->right) { midvalue = root->left->val; } //最终累加求和 int sum = midvalue + leaftvalue + rightvalue; return sum; } }; class Solution { public: int sumOfLeftLeaves(TreeNode* root) { return root ? dfs(root) : 0; } int dfs(TreeNode* root) { int ans = 0; if(root->left) ans += isLeaves(root->left) ? root->left->val : dfs(root->left); if(root->right && !isLeaves(root->right)) ans += dfs(root->right); return ans; } bool isLeaves(TreeNode* root) { return root->left == NULL && root->right == NULL; } };
时间复杂度:O(n),其中 n是树中的节点个数。
空间复杂度:O(n)。空间复杂度与深度优先搜索使用的栈的最大深度相关。在最坏的情况下,树呈现链式结构,深度为 O(n),对应的空间复杂度也为 O(n)。
这篇关于[C++]LeetCode404. 左叶子之和的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-04el-table 开启定时器下,表格的选中状态会消失是什么原因-icode9专业技术文章分享
- 2024-10-03如何安装和初始化飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03如何安装 App 并连接到飞牛 NAS?-icode9专业技术文章分享
- 2024-10-03如何安装飞牛 TV 并连接到影视服务器?-icode9专业技术文章分享
- 2024-10-03如何在PVE和ESXI上安装飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS安装系统异常情况处理-icode9专业技术文章分享
- 2024-10-03飞牛NAS如何创建存储空间?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS硬盘会自动休眠吗?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何安装飞牛影视和创建媒体库?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何为家人朋友开通影视账号?-icode9专业技术文章分享