LeetCode - Tree

---

Tree

Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

1315. Sum of Nodes with Even-Valued Grandparent

class Solution:
    def sumOfGrandson(self, root: TreeNode) -> int:
        ret = 0
        if root.left:
            if root.left.left:
                ret += root.left.left.val
            if root.left.right:
                ret += root.left.right.val
        if root.right:
            if root.right.left:
                ret += root.right.left.val
            if root.right.right:
                ret += root.right.right.val
        return ret
    
    def sumEvenGrandparent(self, root: TreeNode) -> int:
        ret = 0
        if not root:
            return 0
        if root.val % 2 == 0:
            ret += self.sumOfGrandson(root)
        ret += self.sumEvenGrandparent(root.left) + self.sumEvenGrandparent(root.right)
        return ret
            

One-line 算法

Intuition
Let children know who their grandparent is.

Explanation
Assume root has parent.val = 1 and grandparent.val = 1.
Recursive iterate the whole tree and pass on the value of parent and grandparent.
Count the root.val when grandparant if odd-valued.

Complexity
Time O(N)
Space O(height)

def sumEvenGrandparent(self, root, p=1, gp=1):
    return self.sumEvenGrandparent(root.left, root.val, p) \
        + self.sumEvenGrandparent(root.right, root.val, p) \
        + root.val * (1 - gp % 2) if root else 0