Leetcode Contest 29
今晚有鱼、豆腐和西芹。
这次比赛是久违的全一次就AC了,开心😎
第一题Binary Tree Tilt
感觉是简单的dfs套路。对于每个节点,递归算左右子树之和,那么它的tilt值就很容易求出来加到一个全局的变量里,然后返回当前子树之和:左子树+右子树+根节点
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def findTilt(self, root):
"""
:type root: TreeNode
:rtype: int
"""
ans = [0]
def dfs(root):
if not root:
return 0
left = dfs(root.left)
right = dfs(root.right)
ans[0] += abs(left-right)
return left+right+root.val
dfs(root)
return ans[0]