39 Sum of Nodes with Even-Valued Grandparent
为啥没有38?
因为38没过审。
今天点了十张图,登陆上了。
题目
Given a binary tree, return the sum of values of nodes with even-valued grandparent. (A grandparent of a node is the parent of its parent, if it exists.)
If there are no nodes with an even-valued grandparent, return 0.
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.
Constraints:
The number of nodes in the tree is between 1 and 10^4.
The value of nodes is between 1 and 100.
分析
题意:如果当前节点父节点的父节点是偶数,那就把当前节点累加到结果中。
个人理解,这道题考察的是实现(在递归中的)记忆功能。
最简单的想法:
为每一个节点赋予一个deep变量进行深度记录。
如果当前节点为偶数,就往下进入两层,通过deep记录深度;
如果上述操作成功,就将该“孙子”节点值累加到结果中。
但是,事先并不知道节点数是多少,因此deep的个数不能事先确定。
如果使用局部变量…
打住!
想复杂了,就是简单的传值。
正常情况下,当前节点只能知道自己的儿子是谁(root.left\right),无法知道自己的父亲,更不能知道自己的爷爷。
但是,我们调用的时候,可以“把父亲传递下去”,父传子,子传孙。同理孙找父,再找爷爷,只需要顺着这条继承链上来就行了。
解答
把父亲传递下去
算法中也传递了爷爷,但是实际上传递的还是当前类的父亲。当前状态实际是在父亲这一辈。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
int sum=0;
public int sumEvenGrandparent(TreeNode root) {
// 一开始root是祖宗,没有父亲,也没有爷爷
helper(root, -1, -1);
return sum;
}
// node:当前的你、p:爸爸、gp:爷爷
public void helper(TreeNode node, int p, int gp) {
if (node == null) return;
// 如果爷爷是偶数,符合题意,把你加到结果集
if(gp%2==0) sum+=node.val;
// 你的左(右)二子,你爸,你爸的爸爸(爷爷)
helper(node.left,node.val,p);
helper(node.right,node.val,p);
}
}
上一篇: 记一次springboot + Druid + mybatis的大坑
下一篇: 力扣--累加数