欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

39 Sum of Nodes with Even-Valued Grandparent

程序员文章站 2022-07-15 11:36:23
...

为啥没有38?
因为38没过审。
39 Sum of Nodes with Even-Valued Grandparent今天点了十张图,登陆上了。

题目

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:

39 Sum of Nodes with Even-Valued Grandparent

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);
    }
}