from pyparsing import Word, OneOrMore, Group, Suppress, alphanums, oneOf, alphas, Optional, lineEnd
def convert_prop_to_dict(tokens):
    prop_dict = {}
    for token in tokens:
        prop_dict[token[0]] = token[1]
    return prop_dict
# Suppress 表示不捕获
newline = Suppress(lineEnd)
colon = Suppress(":")
arrow = Suppress("->")
semicolon = Suppress(";")
word = Word(alphas)
key = word
value = Word(alphanums)
field_type = oneOf("CharField EmailField PasswordField")
field_name = word
form_name = word.setResultsName("form_name")
field_property = Group(key + colon + value)
field = Group(field_name + colon + field_type + Optional(arrow + OneOrMore(field_property) + semicolon).setParseAction(
        convert_prop_to_dict))
form = form_name + newline + OneOrMore(field).setResultsName("form_field")
input_form = '''
UserForm
username:CharField -> label:Username size:25;
email:EmailField -> size:32;
password:PasswordField;
'''
'''
External DSL
'''
def get_field_html(field):
    properties = field[2]
    label = properties["label"] if "label" in properties else field[0]
    label_html = "<label>" + label + "</label>"
    attributes = {"name": field[0]}
    attributes.update(properties)
    if field[1] == "CharField" or field[1] == "EmailField":
        attributes["type"] = "text"
    else:
        attributes["type"] = "password"
    if "label" in attributes:
        del attributes["label"]
    attributes_html = " ".join([name + "='" + value + "'" for name, value in attributes.items()])
    field_html = "<input " + attributes_html + "/>"
    return label_html + field_html + "<br/>"
def render(form):
    fields_html = "".join([get_field_html(field) for field in form.form_field])
    return "<form id='" + form.form_name.lower() + "'>" + fields_html + "</form>"
print(render(form.parseString(input_form)))
'''
Internal DSL
'''
class HtmlElement(object):
    default_attributes = {}
    tag = "unknown_tag"
    def __init__(self, *args, **kwargs):
        self.attributes = kwargs
        self.attributes.update(self.default_attributes)
        self.children = args
    def __str__(self):
        attribute_html = " ".join(["{}='{}'".format(name, value)
                                   for name, value in self.attributes.items()])
        if not self.children:
            return "<{} {}/>".format(self.tag, attribute_html)
        else:
            children_html = "".join([str(child) for child in self.children])
            return "<{} {}>{}</{}>".format(self.tag, attribute_html, children_html, self.tag)
# print(HtmlElement(id="test"))
# <unknown_tag id='test'/>
# print (HtmlElement(HtmlElement(name="test"), id="id"))
# <unknown_tag id='id'><unknown_tag name='test'/></unknown_tag>
class InputElement(HtmlElement):
    tag = "input"
    def __init__(self, *args, **kwargs):
        HtmlElement.__init__(self, *args, **kwargs)
        self.label = self.attributes["label"] if "label" in self.attributes else self.attributes["name"]
        if "label" in self.attributes:
            del self.attributes["label"]
    def __str__(self):
        label_html = "<label>{}</label>".format(self.label)
        return label_html + HtmlElement.__str__(self) + "<br/>"
# print(InputElement(name="username"))
# <label>username</label><input name='username'/><br/>
# print(InputElement(name="username", label="User ID"))
# <label>User ID</label><input name='username'/><br/>
class Form(HtmlElement):
    tag = "form"
class CharField(InputElement):
    default_attributes = {"type": "text"}
class EmailField(CharField):
    pass
class PasswordField(InputElement):
    default_attributes = {"type": "password"}
def render(form):
    field_dict = {"CharField": CharField, "EmailField":
        EmailField, "PasswordField": PasswordField}
    fields = [field_dict[field[1]](name=field[0], **field[2]) for field in form.form_field]
    return Form(*fields, id=form.form_name.lower())
print(render(form.parseString(input_form)))

# coding:utf-8
class Singleton(object):
    def __new__(cls):
        if not hasattr(cls, 'instance'):
            cls.instance = super(Singleton, cls).__new__(cls)
        return cls.instance
s = Singleton()
print("Object created", s)
s1 = Singleton()
print("Object created", s1)
Object created <__main__.Singleton object at 0x000001B2A199A630>
Object created <__main__.Singleton object at 0x000001B2A199A630>
#### Lazy instantiation版
class Singleton:
    __instance = None
    def __init__(self):
        if not Singleton.__instance:
            print(" __init__ method called..")
        else:
            print("Instance already created:", self.getInstance())
    @classmethod
    def getInstance(cls):
        if not cls.__instance:
            cls.__instance = Singleton()
        return cls.__instance
# s = Singleton.getInstance()
# print("Object created", s)
# s1 = Singleton.getInstance()
# print("Object created", s1)

'''
单例模式要求每一个类只有一个实例，通常来说，我们更需要的是所有实例都共享同一个状态
Python中使用__dict__去存储对象的所有状态
'''
class Borg:
    __shared_state = {"1": "2"}
    def __init__(self):
        self.x = 1
        self.__dict__ = self.__shared_state
        pass
# 我们也可以在__new__中调整
class Borg(object):
    _shared_state = {}
    def __new__(cls, *args, **kwargs):
        obj = super(Borg, cls).__new__(cls, *args, **kwargs)
        obj.__dict__ = cls._shared_state
        return obj
# b = Borg()
# b1 = Borg()
# b.x = 4
# print("Borg Object 'b': ", b) ## b and b1 are distinct objects
# print("Borg Object 'b1': ", b1)
# print("Object State 'b':", b.__dict__) ## b and b1 share same state
# print("Object State 'b1':", b1.__dict__)

'''
元类是类的类(a class of a class)，这意味着类是元类的实例
Python里面万物皆对象。
a=5,type(a) 返回 <type 'int'> 意味着 a 是int类型
type(int) 返回 <type 'type'> 意味着 int 是type类型
我们可以用type生成一个类
A = type(name, bases, dict)
name：生成的类名
bases：基类
dict：类的字典，各种属性等
'''
class MetaSingleton(type):
    _instances = {}
    def __call__(cls, *args, **kwargs):
        if cls not in cls._instances:
            cls._instances[cls] = super(MetaSingleton, cls).__call__(*args, **kwargs)
        return cls._instances[cls]
class Logger(metaclass=MetaSingleton):
    pass
# logger1 = Logger()
# logger2 = Logger()
# print(logger1, logger2)

import sqlite3
class MetaSingleton(type):
    _instances = {}
    def __call__(cls, *args, **kwargs):
        if cls not in cls._instances:
            cls._instances[cls] = super(MetaSingleton, cls).__call__(*args, **kwargs)
        return cls._instances[cls]
class Database(metaclass=MetaSingleton):
    connection = None
    def connect(self):
        if self.connection is None:
            self.connection = sqlite3.connect("db.sqlite3")
            self.cursorobj = self.connection.cursor()
        return self.cursorobj
db1 = Database().connect()
db2 = Database().connect()
print("Database Objects DB1", db1)
print("Database Objects DB2", db2)

# coding:utf-8
class Node(object):
    def __init__(self, key):
        self.key1 = key
        self.key2 = None
        self.left = None
        self.middle = None
        self.right = None
    def isLeaf(self):
        return self.left is None and self.middle is None and self.right is None
    def isFull(self):
        return self.key2 is not None
    def hasKey(self, key):
        if (self.key1 == key) or (self.key2 is not None and self.key2 == key):
            return True
        else:
            return False
    def getChild(self, key):
        if key < self.key1:
            return self.left
        elif self.key2 is None:
            return self.middle
        elif key < self.key2:
            return self.middle
        else:
            return self.right
class two_three_Tree(object):
    def __init__(self):
        self.root = None
    def get(self, key):
        if self.root is None:
            return None
        else:
            return self._get(self.root, key)
    def _get(self, node, key):
        if node is None:
            return None
        elif node.hasKey(key):
            return node
        else:
            child = node.getChild(key)
            return self._get(child, key)
    def put(self, key):
        if self.root is None:
            self.root = Node(key)
        else:
            pKey, pRef = self._put(self.root, key)
            if pKey is not None:
                newnode = Node(pKey)
                newnode.left = self.root
                newnode.middle = pRef
                self.root = newnode
    def _put(self, node, key):
        # 不重复的key
        if node.hasKey(key):
            return None, None
        # 叶节点，直接插入
        elif node.isLeaf():
            return self._addtoNode(node, key, None)
        # 遍历子树，直到遇到叶节点
        else:
            child = node.getChild(key)
            pKey, pRef = self._put(child, key)
            # 有 pKey, pRef 表示进行了分割
            # pKey 表示往上移的key
            # pRef 表示newnode
            # 每次 _addtoNode 到一个 3-Node的时候,肯定会有pKey和pRef(因为需要分割上移)
            if pKey is None:
                return None, None
            else:
                return self._addtoNode(node, pKey, pRef)
    def _addtoNode(self, node, key, pRef):
        # 3-Node，分割
        if node.isFull():
            return self._splitNode(node, key, pRef)
        # 2-Node
        else:
            # 放入该node的左边
            if key < node.key1:
                node.key2 = node.key1
                node.key1 = key
                # 如果该node有子树
                if pRef is not None:
                    node.right = node.middle
                    node.middle = pRef
            else:
                node.key2 = key
                if pRef is not None:
                    node.right = pRef
            # pKey, pRef
            return None, None
    def _splitNode(self, node, key, pRef):
        # 这是难点,请对照插入的图例,认真学习
        newnode = Node(None)
        if key < node.key1:
            # x是最小的key，把key1移上去
            pKey = node.key1
            node.key1 = key
            newnode.key1 = node.key2
            if pRef is not None:
                newnode.left = node.middle
                newnode.middle = node.right
                node.middle = pRef
        elif key < node.key2:
            # x是中间的key,把自己移上去
            pKey = key
            newnode.key1 = node.key2
            if pRef is not None:
                newnode.left = pRef
                newnode.middle = node.right
        else:
            # x是最大的key,把key2
            pKey = node.key2
            newnode.key1 = key
            if pRef is not None:
                newnode.left = node.right
                newnode.middle = pRef
        node.key2 = None
        return pKey, newnode

'''
问题1:
dp[i][j]的含义，在可以任意使用arr[0...i]货币的情况下，组成j所需的最小张数
假设计算到位置(i,j),dp[i][j]的值可能来自下面的情况
1.完全不使用当前货币arr[i]的情况下的最少张数,即dp[i-1][j]
2.使用1张货币arr[i]的情况下的最少张数,即dp[i-1][j-arr[i]]+1
3.使用2张货币arr[i]的情况下的最少张数,即dp[i-1][j-2*arr[i]]+2
4.使用3张货币arr[i]的情况下的最少张数,即dp[i-1][j-3*arr[i]]+3
dp[i][j] = min(dp[i-1][j], dp[i][j-arr[i]]+1)
位置i,j依赖位置(i-1,j)，即往上跳一下的位置，也依赖位置(i,j-arr[i])，即往左跳一下的位置
时间复杂度，空间复杂度O(N*aim)
'''
def minCoins1(arr, aim):
    n = len(arr)
    inf = float('inf')
    dp = [[0] * (aim + 1) for i in range(n)]
    # 初始化第一行
    for j in range(1, aim + 1):
        dp[0][j] = inf
        if j - arr[0] >= 0 and dp[0][j - arr[0]] != inf:
            dp[0][j] = dp[0][j - arr[0]] + 1
    for i in range(1, n):
        for j in range(1, aim + 1):
            # j = (j - arr[i]) + arr[i]
            # 注意到j - arr[i]位置上(j - arr[i]元)，必须不为inf（即，可以用arr[0~i]货币找开)
            left = dp[i][j - arr[i]] + 1 \
                if j - arr[i] >= 0 and dp[i][j - arr[i]] != inf \
                else inf
            # 左边跟上边(用arr[0~i-1]货币找开)比
            dp[i][j] = min(left, dp[i - 1][j])
    return dp[n - 1][aim] if dp[n - 1][aim] != inf else -1
# 空间压缩
def minCoins2(arr, aim):
    n = len(arr)
    inf = float('inf')
    dp = [0] * (aim + 1)
    for j in range(1, aim + 1):
        dp[j] = inf
        if j - arr[0] >= 0 and dp[j - arr[0]] != inf:
            dp[j] = dp[j - arr[0]] + 1
    for i in range(1, n):
        for j in range(1, aim + 1):
            left = dp[j - arr[i]] + 1 \
                if j - arr[i] >= 0 and dp[j - arr[i]] != inf \
                else inf
            # (i,j)的左边(j-arr[i])跟上面(i-1,j)比较
            dp[j] = min(left, dp[j])
    return dp[aim] if dp[aim] != inf else -1
'''
问题2
dp[i][j]的含义，在可以任意使用arr[0...i]货币的情况下（每个值权代表一张货币），组成j所需的最小张数
如，dp[0][0...aim]，表示只能使用一张arr[0]货币的情况下，找某个钱数的最小张数。
假设计算到位置(i,j),dp[i][j]的值可能来自下面的情况
1.上边，对于dp[i-1][j]表示，任意使用arr[0...i-1]货币的情况下，组成j所需的最小张数，dp[i][j]可能与其相等
2.左上边，因为arr[i]只有一张不能重复，我们考虑dp[i-1][j-arr[i]],表示在可以任意使用arr[0...i-1]货币的情况下，组成j-arr[i]所需的最小张数。
所以dp[i][j]=dp[i-1][j-arr[i]]+1
注意，本题不能像minCoins2那样使用空间压缩。
因为在dp[j - arr[i]]的使用，可能已经使用了当前的货币i
如，本题的例子
在i=2,j=6的时候 dp[6]，其dp[j - arr[i]]=dp[3]=1，已经使用过了货币3。所以无法重复使用。
'''
def minCoins3(arr, aim):
    n = len(arr)
    inf = float('inf')
    dp = [[0] * (aim + 1) for i in range(n)]
    # 第0行的初始化，除了使用货币自身(arr[0])，其他都为inf
    for j in range(1, aim + 1):
        dp[0][j] = inf
    if arr[0] <= aim:
        dp[0][arr[0]] = 1
    for i in range(1, n):
        for j in range(1, aim + 1):
            leftup = dp[i - 1][j - arr[i]] + 1 \
                if j - arr[i] >= 0 and dp[i - 1][j - arr[i]] != inf \
                else inf
            dp[i][j] = min(leftup, dp[i - 1][j])
    return dp[n - 1][aim] if dp[n - 1][aim] != inf else -1

# coding:utf-8
test = [
    [1, 3, 5, 9],
    [8, 1, 3, 4],
    [5, 0, 6, 1],
    [8, 8, 4, 0]
]
def getMost(border):
    each_path = []
    col = len(border[0])
    row = len(border)
    def most_momey(i=0, j=0, the_sum=0):
        # 向右走
        if j < col - 1:
            most_momey(i, j + 1, border[i][j] + the_sum)
        # 向左走
        if i < row - 1:
            most_momey(i + 1, j, border[i][j] + the_sum)
        # 到达右下角
        if i == row - 1 and j == col - 1:
            each_path.append(the_sum + border[i][j])
        else:
            return
    most_momey()
    return max(each_path)

'''
根据题意，从(0,0)到(i,j)的路径必然经过位置(i-1,j)或(i,j-1)。
dp[n][m] = max(dp[n - 1][m], dp[n][m - 1]) + border[n][m]
的含义也就是比较从(0,0)位置开始，经过(i-1,j)位置最终到达(i,j)的最大路径和经过(i,j-1)位置最终到达(i,j)的最大路径之间，哪条路径的路径和最大
就题目中的例子，我们先生成第一行和第一列的dp，也就是
1   4   9   18
9
14
22
然后从(1,1)开始，计算从(0,0)到自己的最大路径和，计算的时候只是比较上边和左边哪个最大。
时间复杂度O(M*N)，空间复杂度O(M*N)
'''
def getMost_dp(border):
    col = len(border[0])
    row = len(border)
    # dp标识走到(i,j)位置的最大路径和
    dp = [[0] * col for i in range(row)]
    dp[0][0] = border[0][0]
    # 求出dp[0][1]-dp[0][col]
    for i in range(1, col):
        dp[0][i] = dp[0][i - 1] + border[0][i]
    # 求出dp[1][0]-dp[row][0]
    for j in range(1, row):
        dp[j][0] = dp[j - 1][0] + border[j][0]
    for n in range(1, row):
        for m in range(1, col):
            dp[n][m] = max(dp[n - 1][m], dp[n][m - 1]) + border[n][m]
    return dp[row - 1][col - 1]
# print getMost_dp(test)
'''
空间压缩
上述的代码，空间复杂度为O(M*N)，我们还可以对其进行空间压缩，使复杂度降到O(min{M,N})
就上面的例子，我们先生成一个arr[min(rol,row)]数组。在这个例子里面是arr[4]
我们根据row和col的数量进行滚动，row多的话，向下滚动；否则向右滚动。
我们这里向下滚动。
所以求出arr[i] = arr[i - 1] + border[0][i] = [1,4,9,18]
然后我们向下滚动i=1。
arr[0] = arr[0] + border[i][0] = 9
arr[1] = max(arr[1 - 1], arr[1]) + border[i][1]    
# arr[1 - 1], arr[1]分别代表border[i][1]的左边和上边
arr[2] = max(arr[2 - 1], arr[1]) + border[i][2]
....
arr[j] = max(arr[j - 1], arr[j]) + border[i][j]
没有优化之前，取得某个位置动态规划值的过程是在矩阵中进行两次寻址，优化后，这一过程只需要一次寻址。
'''
def getMost_dp2(border):
    col = len(border[0])
    row = len(border)
    more = max(col, row)
    less = min(col, row)
    rowmore = bool(more == len(border))
    arr = [0] * less
    arr[0] = border[0][0]
    # row多的话，向下滚动；否则向右滚动
    for i in range(1, less):
        arr[i] = arr[i - 1] + border[0][i] if rowmore else border[i][0]
    for i in range(1, more):
        arr[0] = arr[0] + border[i][0] if rowmore else border[0][i]
        for j in range(1, less):
            arr[j] = max(arr[j - 1], arr[j]) + border[i][j] if rowmore else border[j][i]
    return arr[less-1]

# coding:utf-8
class BinarySearchTree:
    def __init__(self):
        self.root = None
        self.size = 0
    def length(self):
        return self.size
    def __len__(self):
        return self.size
    def __setitem__(self, k, v):
        self.put(k, v)
    def __getitem__(self, key):
        return self.get(key)
    def __contains__(self, key):
        if self._get(key, self.root):
            return True
        else:
            return False
    def put(self, key, val):
        if self.root:
            self._put(key, val, self.root)
        # 空树
        else:
            self.root = TreeNode(key, val)
        self.size = self.size + 1
    def _put(self, key, val, currentNode):
        # 左子树
        if key < currentNode.key:
            if currentNode.hasLeftChild():
                self._put(key, val, currentNode.leftChild)
            else:
                currentNode.leftChild = TreeNode(key, val, parent=currentNode)
        # 右子树
        else:
            if currentNode.hasRightChild():
                self._put(key, val, currentNode.rightChild)
            else:
                currentNode.rightChild = TreeNode(key, val, parent=currentNode)
    def get(self, key):
        if self.root:
            res = self._get(key, self.root)
            if res:
                return res.payload
            else:
                return None
        else:
            return None
    def _get(self, key, currentNode):
        if not currentNode:
            return None
        elif currentNode.key == key:
            return currentNode
        elif key < currentNode.key:
            return self._get(key, currentNode.leftChild)
        else:
            return self._get(key, currentNode.rightChild)
class TreeNode:
    def __init__(self, key, val, left=None, right=None,
                 parent=None):
        self.key = key
        self.payload = val
        self.leftChild = left
        self.rightChild = right
        self.parent = parent
    def hasLeftChild(self):
        return self.leftChild
    def hasRightChild(self):
        return self.rightChild
    def isLeftChild(self):
        return self.parent and self.parent.leftChild == self
    def isRightChild(self):
        return self.parent and self.parent.rightChild == self
    def isRoot(self):
        return not self.parent
    def isLeaf(self):
        return not (self.rightChild or self.leftChild)
    def hasAnyChildren(self):
        return self.rightChild or self.leftChild
    def hasBothChildren(self):
        return self.rightChild and self.leftChild
    def replaceNodeData(self, key, value, lc, rc):
        self.key = key
        self.payload = value
        self.leftChild = lc
        self.rightChild = rc
        if self.hasLeftChild():
            self.leftChild.parent = self
        if self.hasRightChild():
            self.rightChild.parent = self
if __name__ == '__main__':
    tree = BinarySearchTree()
    for k, v in zip(range(ord('a'), ord('a') + 10), [62, 58, 88, 47, 73, 99, 35, 51, 93, 37]):
        tree.put(v, chr(k))
    print tree[88]

a, b, c, d, e, f, g, h = ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h')
G = {
    a: [b, f],
    b: [c, d, f],
    c: [d],
    d: [e, f],
    e: [f],
    f: []
}
def res_topsort(G, S=None):
    # S是当前规模各个点的集合
    if S is None: S = set(G)
    if len(S) == 1: return list(S)
    # 随意出一点
    v = S.pop()
    seq = res_topsort(G, S)
    min_i = 0
    # 找出以v点为出边的是哪一元素，将其插入该元素后，如无，插入开头
    # 规模从小到大，每一次return 的 seq都是一个DAG
    for i, u in enumerate(seq):
        if v in G[u]: min_i = i + 1
    seq.insert(min_i, v)
    return seq
def topsort(G):
    count = dict((u, 0) for u in G)
    for u in G:
        for v in G[u]:
            count[v] += 1
    Q = [u for u in G if count[u] == 0]
    S = []
    while Q:
        u = Q.pop()
        # 将没有入边的节点插入
        S.append(u)
        # 每出一条边 减少 该没有入边的节点指向的节点 的入边
        for v in G[u]:
            count[v] -= 1
            if count[v] == 0:
                Q.append(v)
    return S
print res_topsort(G)
# ['a', 'b', 'c', 'd', 'e', 'f']

G = {
    0:{},
    1: {1: 1, 2: 2},
    2: {1: 1, 3: 6, 4: 11},
    3: {1: 2, 2: 6, 4: 9, 5: 13},
    4: {2: 11, 3: 9, 5: 7, 6: 3},
    5: {3: 13, 4: 7, 6: 4},
    6: {4: 3, 5: 4},
}
'''
Kruskal算法
各种变量：
C：形如{u1:v1,u2:v2,....}的字典，主要用来寻找代表节点(祖先节点)。初始化，v1=u1,v2=u2....
如a-b-c-d {a:a,b:a,c:b,d:c}
G：图
E：列表，存放着形如(e,u,v)的字典，e：权值，u：源点，v：目标点
'''
def find(C, u):
    '''
寻找代表节点(祖先节点)
这里使用的是路径压缩的方法（path compression）
'''
    if C[u] != u:
        C[u] = find(C, C[u])
    return C[u]
def naive_union(C, u, v):
    '''
把较小的指向较大的
'''
    u, v = find(C, u), find(C, v)
    # u的祖先节点指向v的祖先节点
    C[u] = v
def kruskal(G):
    E = [(G[u][v], u, v) for u, _ in enumerate(G) for v in G[u]]
    T = set()
    C = {u: u for u, _ in enumerate(G)}
    for _, u, v in sorted(E):
        if find(C, u) != find(C, v): # 边的源点的祖先不等于边的目的祖先（因为相等的话说明该点已经添加过了，否则为默认值）
            T.add((u, v)) # 添加
            naive_union(C, u, v) # 合并，使目标节点变成生成树的一部分（修改其祖先）。
    return T,C
# ------测试结果---------
sum_count = 0
T = kruskal(G)
for k, v in T:
    sum_count += G[k][v]
print(sum_count)
print(sorted([i for i in T], key=lambda x: x[1]))
# 结果为19
# [(1, 2), (1, 3), (3, 4), (5, 6), (4, 6)]
# 以下为完成后的中间变量，便于理解
# C={0: 0, 1: 3, 2: 6, 3: 6, 4: 6, 5: 6, 6: 6}

def prim(G, s):
    P, Q = {}, [(0, None, s)]
    while Q:
        w, p, u = heappop(Q)
        if u in P: continue # 如果目标点在生成树中，跳过
        P[u] = p # 记录目标点不在生成树中
        for v, w in G[u].items():
            heappush(Q, (w, u, v)) # 将u点的出边入堆
    return P
# T = prim(G, 1)
# sum_count = 0
# for k, v in T.items():
# if v !=None:
# sum_count += G[k][v]
#
# print(sum_count)
# print(T)
# 结果为19
# {1: None, 2: 1, 3: 1, 4: 3, 5: 6, 6: 4}

class Node:
    def __init__(self, value=None, left=None, right=None):
        self.val = value
        self.left = left
        self.right = right
# TREE = Node(0,
#             Node(1, Node(1), Node(0)),
#             Node(0, Node(0), Node(1))
#             )
TREE = Node(0,
            Node(1, Node(0, Node(1, Node(1))), Node(0)),
            Node(1, Node(0), Node(0))
            )
def func(root):
    B_res, W_res = [], []
    def res(root, W, B):
        if root == None:
            B_res.append(B)
            W_res.append(W)
            return
        if root.val == 0:
            W += 1
            B_res.append(B)
            B = 0
        elif root.val == 1:
            B += 1
            W_res.append(W)
            W = 0
        res(root.left, W, B)
        res(root.right, W, B)
    res(root, 0, 0)
    return max(max(B_res), max(W_res))