LeetCode C++ 1469. Find All The Lonely Nodes【Tree/DFS/BFS】简单
发布日期:2021-07-01 02:58:21
浏览次数:3
分类:技术文章
本文共 1800 字,大约阅读时间需要 6 分钟。
In a binary tree, a lonely node is a node that is the only child of its parent node. The root of the tree is not lonely because it does not have a parent node.
Given the root
of a binary tree, return an array containing the values of all lonely nodes in the tree. Return the list in any order.
Example 1:
Input: root = [1,2,3,null,4]Output: [4]Explanation: Light blue node is the only lonely node.Node 1 is the root and is not lonely.Nodes 2 and 3 have the same parent and are not lonely.
Example 2:
Input: root = [7,1,4,6,null,5,3,null,null,null,null,null,2]Output: [6,2]Explanation: Light blue nodes are lonely nodes.Please remember that order doesn't matter, [2,6] is also an acceptable answer.
Example 3:
Input: root = [11,99,88,77,null,null,66,55,null,null,44,33,null,null,22]Output: [77,55,33,66,44,22]Explanation: Nodes 99 and 88 share the same parent. Node 11 is the root.All other nodes are lonely.
Example 4:
Input: root = [197]Output: []
Example 5:
Input: root = [31,null,78,null,28]Output: [78,28]
Constraints:
- The number of nodes in the
tree
is in the range[1, 1000].
- Each node's value is between
[1, 10^6]
.
题意:给定一棵二叉树的根节点 root
,返回树中 所有的独生节点的值所构成的数组 。数组的顺序 不限 。
解法 DFS
使用DFS,当前节点根据传递下来的信息(这一节点是否是独生节点),决定节点值是否加入结果;然后判断当前节点的左右子节点是否是独生节点,递归调用并传递信息:
class Solution { private: vector ans; void dfs(TreeNode* root, bool isLone) { if (root == nullptr) return; if (isLone) ans.push_back(root->val); //是独生节点 bool flag = (root->left && !root->right) || (!root->left && root->right); dfs(root->left, flag); dfs(root->right, flag); }public: vector getLonelyNodes(TreeNode* root) { dfs(root, false); return ans; }};
运行效率如下:
执行用时:24 ms, 在所有 C++ 提交中击败了81.15% 的用户内存消耗:20.4 MB, 在所有 C++ 提交中击败了30.58% 的用户
转载地址:https://memcpy0.blog.csdn.net/article/details/111404752 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年04月16日 12时11分55秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
C/C++如何返回一个数组/指针
2019-04-30
腾讯AI语音识别API踩坑记录
2019-04-30
java.net.BindException: 无法指定被请求的地址
2019-05-01
svn服务器安装
2019-05-01
spark 笔记1
2019-05-01
shell dirname basename
2019-05-01
未来已至,5G加持下的云游戏将走向何方?
2019-05-01
计算机网络 —— 网络层 1.
2019-05-01
Android 之 ContentProvider 与 ContentResolver
2019-05-01
【接口自动化】
2019-05-01
推荐一位川大零基础转行 Python 的人生勇士
2019-05-01
Python解惑之:True与False
2019-05-01
你要的微信小程序终于来了
2019-05-01
有了这些 Chrome 插件,效率提升10倍(建议收藏)
2019-05-01
只有1%的程序员搞懂过浮点数陷阱
2019-05-01
一名 Google 工程师的大数据处理经验
2019-05-01
命名难,难于上青天
2019-05-01
没钱没公司,怎么做一款付费产品
2019-05-01
代码整洁之道-编写 Pythonic 代码
2019-05-01