从一道题说Python闭包、盒猴子补丁、作用域

一道题

今天做LeetCode周赛，真是诸事不顺，创下了历史记录新低。先是开赛了五分钟题目才显示出来，接着是第一道题就被卡住，然后在结束之后1分钟做出来第三题，怎么一个惨淡了得。今天要谈的就是我被卡住的第一题。

Given a binary tree, return the tilt of the whole tree.

The tilt of a tree node is defined as the absolute difference between the sum of all left subtree node values and the sum of all right subtree node values. Null node has tilt 0.

The tilt of the whole tree is defined as the sum of all nodes' tilt.

Input: 
         1
       /   \
      2     3
Output: 1
Explanation: 
Tilt of node 2 : 0
Tilt of node 3 : 0
Tilt of node 1 : |2-3| = 1
Tilt of binary tree : 0 + 0 + 1 = 1

闭包与作用域

首先我就理解错了题意，以为tilt是abs(left.val - right.val)不用考虑left和right的子节点，实际上是abs(sum(left)-sum(right)), 在这样的情况下，我很快写出一个递归函数来求解：

    def findTilt(self, root):
        if not root: return 0
        c = 0
        def r(node):
            left = node.left.val if node.left else 0
            right = node.right.val if node.right else 0
            c += abs(left - right)
            if node.left: r(node.left)
            if node.right: r(node.right)
        r(root)
        return c0

这里很快的就遇到了问题，IDE告诉我无法识别内部函数里面的c，这让我大吃一惊，在我的平时的意识里，内部的函数应该能够访问外部的变量，但是这里却爆出了错误，查阅资料后明白这是因为c是不可变的数字类型，而我平时使用时一般是集合类型。要解决这个问题一般有两种方法，在python3后面的版本当中可以使用nonlocal关键字，python2当中可以把c = 0改为c = [0]。

其实这个问题我曾经在fluent Python当中看到过，但是却没有留下深刻的印象，这次相信映像会比较深刻，在解决到了这个我开始面临刚才提到的理解错题意的问题。

猴子补丁

意思到问题之后，我发现需要计算每个子树的和，当然可以用其他比较简单的方法，这里我灵机一动，想到了猴子补丁，猴子补丁允许在运行时给已经定义的类添加属性，最后我又写了一个递归函数为每个节点加了一个sum属性，最后的解决方案如下;

class Solution(object):
    def findTilt(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root: return 0
        TreeNode.sum = 0
        c = [0]
        def s(node):
            node.sum = 0
            if node.left: node.sum += s(node.left)
            if node.right: node.sum += s(node.right)
            return node.sum
        def r(node):
            left = node.left.sum if node.left else 0
            right = node.right.sum if node.right else 0
            c[0] += abs(left - right)
            if node.left: r(node.left)
            if node.right: r(node.right)
        s(root)
        r(root)
        return c[0]

总结

这次映像确实还是挺深刻的，有很多经验教训值的总结，第一是应该先理解题意，不要急，因为最开始有好几分钟都没有显示试题，所以在最开始的时候会有点急躁，结果导致耽误了更多的时间。第二是纸上得来终觉浅，绝知此事要躬行，光看一遍很难有深刻的映象，需要不断的实践，经典的书籍页需要不断的重读。