[LeetCode] 1315. Sum of Nodes with Even-Valued Grandparent 祖父节点值为偶数的节点和
2022/8/31 14:22:57
本文主要是介绍[LeetCode] 1315. Sum of Nodes with Even-Valued Grandparent 祖父节点值为偶数的节点和,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Given the root
of a binary tree, return the sum of values of nodes with an even-valued grandparent. If there are no nodes with an even-valued grandparent, return 0
.
A grandparent of a node is the parent of its parent if it exists.
Example 1:
Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5] Output: 18 Explanation: The red nodes are the nodes with even-value grandparent while the blue nodes are the even-value grandparents.
Example 2:
Input: root = [1] Output: 0
Constraints:
- The number of nodes in the tree is in the range
[1, 104]
. 1 <= Node.val <= 100
这道题给了一棵二叉树,让返回具有偶数值爷结点的所有结点的值之和,何为爷结点,就是父结点的父结点。需要找出所有爷结点值是偶数的结点,并返回它们的结点值之和,注意不是返回爷结点值之和。根据以往的经验,二叉树的题目大多情况下都是用递归的解法,这道题也不例外,遍历顺序就用先序遍历就可以了。在递归函数中,首先判空,若为空,直接返回。否则看当前结点值是否为偶数,是的话就去找其孙结点,一共有四个孙结点,若左子结点存在的话,分别判断其两个孙结点是否存在,存在的话就将其结点值加到 res 中,同理,若右子结点存在的话,分别判断其两个孙结点是否存在,存在的话就将其结点值加到 res 中,然后在分别对左右子结点调用递归函数即可,参见代码如下:
解法一:
class Solution { public: int sumEvenGrandparent(TreeNode* root) { int res = 0; dfs(root, res); return res; } void dfs(TreeNode* node, int& res) { if (!node) return; if (node->val % 2 == 0) { if (node->left) { if (node->left->left) res += node->left->left->val; if (node->left->right) res += node->left->right->val; } if (node->right) { if (node->right->left) res += node->right->left->val; if (node->right->right) res += node->right->right->val; } } dfs(node->left, res); dfs(node->right, res); } };
上面解法的判断有些复杂,这是因为是在找当前结点的四个孙结点,若是直接处理每个孙结点的话,就会相对简单一些。但此时必须要知道孙结点的爷结点,同时也要知道父结点,因为一旦去递归子结点时,之前的父结点就是新的爷结点,所以在递归函数中要把父结点和爷结点当参数传进去。在递归函数中还是先判空,然后判断若爷结点存在,并且值为偶数,则将当前结点值加到 res 中,然后分别对左右子结点调用递归函数,当前结点和父结点就变成了新的父结点和爷结点当参数传入即可,参见代码如下:
解法二:
class Solution { public: int sumEvenGrandparent(TreeNode* root) { int res = 0; dfs(root, nullptr, nullptr, res); return res; } void dfs(TreeNode* node, TreeNode* parent, TreeNode* grandParent, int& res) { if (!node) return; if (grandParent && grandParent->val % 2 == 0) { res += node->val; } dfs(node->left, node, parent, res); dfs(node->right, node, parent, res); } };
Github 同步地址:
https://github.com/grandyang/leetcode/issues/1315
参考资料:
https://leetcode.com/problems/sum-of-nodes-with-even-valued-grandparent/
https://leetcode.com/problems/sum-of-nodes-with-even-valued-grandparent/discuss/477095/Easy-DFS-solution
https://leetcode.com/problems/sum-of-nodes-with-even-valued-grandparent/discuss/477048/JavaC%2B%2BPython-1-Line-Recursive-Solution
LeetCode All in One 题目讲解汇总(持续更新中...)
这篇关于[LeetCode] 1315. Sum of Nodes with Even-Valued Grandparent 祖父节点值为偶数的节点和的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升