class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right

    def __repr__(self):
        return 'Node val = {}'.format(str(self.val))

'''
紧凑型顺序存储
参考资料： https://leetcode.com/explore/learn/card/data-structure-tree/133/conclusion/995/discuss
测试： https://leetcode-cn.com/problems/serialize-and-deserialize-bst/submissions/
'''
class Codec:
    def serialize(self, root: TreeNode) -> str:
        queue = [root]
        res = []
        while queue:
            new_queue = []
            for node in queue:
                res.append(node)
                if node is not None:
                    new_queue.append(node.left)
                    new_queue.append(node.right)
            queue = new_queue
        return ','.join([str(node.val) if node else '#' for node in res])

    def deserialize(self, data: str) -> TreeNode:
        nodes = [None if val == '#' else TreeNode(int(val)) for val in data.split(',')]
        queue = nodes[::-1]
        root = queue.pop()
        for node in nodes:
            if node:
                if queue: node.left = queue.pop()
                if queue: node.right = queue.pop()
        return root

# DFS用递归实现更可维护，但也可以用 stack 实现
# BFS用队列实现更可维护，但也可以用递归
class Travel:

  def ldr(self, root):  # InOrder
      res = []

      def _ldr(node):
          if node:
              _ldr(node.left)
              res.append(node.val)
              _ldr(node.right)

      _ldr(root)
      return res

  def dlr(self, root):  # PreOrder
      res = []

      def _dlr(node):
          if node:
              res.append(node.val)
              _dlr(node.left)
              _dlr(node.right)

      _dlr(root)
      return res

  def lrd(self, root):  # PostOrder
      res = []

      def _lrd(node):
          if node:
              _lrd(node.left)
              _lrd(node.right)
              res.append(node.val)

      _lrd(root)
      return res


    def level_order(self, root):
        # BFS, tree转稀疏型顺序存储。
        q, ret = [root], []
        while any(q):
            ret.extend([node.val if node else None for node in q])
            q = [child for node in q for child in [node.left if node else None, node.right if node else None]]
        return ret

    def level_order2(self, root):
        # BFS, tree转紧凑型顺序存储。
        q, ret = [root], []
        while any(q):
            ret.extend([node.val if node else None for node in q])
            q = [child for node in q if node for child in [node.left, node.right]]
        # 结尾的 None 无意义，清除掉
        while ret[-1] is None:
            ret.pop()
        return ret

    def level_order3(self, root):
        """
        队列实现，待整理，这个返回值是有结构的list，其实 level_order2 也可以轻松改造
        https://leetcode.com/problems/binary-tree-level-order-traversal/description/
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if root is None:
            return []
        import collections
        level = 0
        deque = collections.deque([(root,0)])
        output=[]
        while deque:
            tmp_root,level = deque.popleft()
            if tmp_root.left: deque.append((tmp_root.left,level+1))
            if tmp_root.right: deque.append((tmp_root.right,level+1))
            if len(output)<=level:
                output.append([tmp_root.val])
            else:
                output[level].append(tmp_root.val)
        return output


    def level_order_nary(self, root):
        # 针对N-ary Tree的方法，非常漂亮，前面几个 level_order 都是参考这个
        # https://leetcode.com/problems/n-ary-tree-level-order-traversal/description/
        q, ret = [root], []
        while any(q):
            ret.append([node.val for node in q])
            q = [child for node in q for child in node.children if child]
        return ret

    def find_track(self, num, root, track_str=''):
        '''
        二叉树搜索
        '''
        track_str = track_str + str(root.val)
        if root.val == num:
            return track_str
        if root.left is not None:
            self.find_track(num, root.left, track_str + ' ->left-> ')
        if root.right is not None:
            self.find_track(num, root.right, track_str + ' ->right-> ')

class BuildTree:
    def build_tree_from_ldr_lrd(self, inorder, postorder):
        """
        https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/
        已知中序+后序结果，确定这棵树，前提是list中没有重复的数字
        :type inorder: List[int]
        :type postorder: List[int]
        :rtype: TreeNode
        """
        if not inorder or not postorder:
            return None
        root = TreeNode(postorder.pop())
        inorder_index = inorder.index(root.val)

        root.right = self.build_tree_from_ldr_lrd(inorder[inorder_index + 1:], postorder)
        root.left = self.build_tree_from_ldr_lrd(inorder[:inorder_index], postorder)

        return root

    def build_tree_from_dlr_ldr(self, preorder, inorder):
        """
        https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/
        前序+中序确定一棵树，前提是list中没有重复的数字
        TODO: pop(0)效率很低，看看怎么解决
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        if not preorder or not inorder:
            return None
        root = TreeNode(preorder.pop(0))
        inorder_index = inorder.index(root.val)

        root.left = self.build_tree_from_dlr_ldr(preorder, inorder[:inorder_index])
        root.right = self.build_tree_from_dlr_ldr(preorder, inorder[inorder_index + 1:])
        return root

    preIndex, posIndex = 0, 0
    def constructFromPrePost(self, pre, post):
      """
      pre+post 确定一个树
      https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/
      """
        root = TreeNode(pre[self.preIndex])
        self.preIndex += 1
        if (root.val != post[self.posIndex]):
            root.left = self.constructFromPrePost(pre, post)
        if (root.val != post[self.posIndex]):
            root.right = self.constructFromPrePost(pre, post)
        self.posIndex += 1
        return root

class BST
    def sorted2BST(self, nums):
        """
        从一个sorted list生成平衡的BST
        https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description/
        :type nums: List[int]
        :rtype: TreeNode
        """
        if not nums:
            return None
        mid = len(nums) // 2
        return TreeNode(val=nums[mid], left=self.sorted2BST(nums[:mid]), right=self.sorted2BST(nums[mid + 1:]))

    def isValidBST(self, root):
        # 判断是否是BST，返回 True/False
        inorder = self.inorder(root)
        return inorder == list(sorted(set(inorder)))

    def searchBST(self, root, val):
        # 搜索 BST，如果val在 BST中，返回对应节点，否则返回None
        if root and val < root.val:
            return self.searchBST(root.left, val)
        elif root and val > root.val:
            return self.searchBST(root.right, val)
        return root

    def insertIntoBST(self, root, val):
        """
        把值 val 插入到BST中
        :type root: TreeNode
        :type val: int
        :rtype: TreeNode
        """
        if root is None:
            return TreeNode(val)
        if root.val < val:
            root.right = self.insertIntoBST(root.right, val)
        elif root.val > val:
            root.left = self.insertIntoBST(root.left, val)
        return root

    def deleteNode(self, root, key):
        """
        删除节点的方式有很多种：左子节点提升，右子节点提升，下面这个思路是把右子树的最左左叶节点作为替换被删节点的值
        :type root: TreeNode
        :type key: int
        :rtype: TreeNode
        """
        if not root:
            return root
        if root.val > key:
            root.left = self.deleteNode(root.left, key)
        elif root.val < key:
            root.right = self.deleteNode(root.right, key)
        else:
            if not root.right:
                return root.left
            if not root.left:
                return root.right
            else:
                tmp, mini = root.right, root.right.val
                while tmp.left:
                    tmp, mini = tmp.left, tmp.left.val
                root.val = mini
                root.right = self.deleteNode(root.right, root.val)
        return root

# https://leetcode-cn.com/problems/validate-binary-search-tree/
class Solution:
    int_min=-2 ** 32
    int_max=2 ** 32
    def isValidBST(self, root: TreeNode) -> bool:
        res = [True]

        def dfs(node, parent_min, parent_max):
            if res[0] is False:
                return

            if node is None:
                return

            if not parent_min < node.val < parent_max:
                res[0] = False
                return

            dfs(node.left, parent_min, node.val)
            dfs(node.right, node.val, parent_max)

        dfs(root, self.int_min, self.int_max)
        return res[0]

class BSTIterator(object):
    def __init__(self, root):
        """
        :type root: TreeNode
        """
        self.stack=[]
        while root:
            self.stack.append(root)
            root=root.left

    def hasNext(self):
        """
        :rtype: bool
        """
        return len(self.stack)>0

    def next(self):
        """
        :rtype: int
        """
        node=self.stack.pop()
        x=node.right
        while x:
            self.stack.append(x)
            x=x.left
        return node.val

# Your BSTIterator will be called like this:
# i, v = BSTIterator(root), []
# while i.hasNext(): v.append(i.next())

class Solution:
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        if root is None:
            return None

        curr=root
        while curr is not None:
            if curr.val==val:
                return curr
            elif curr.val>val:
                curr=curr.left
            else:
                curr=curr.right

class Solution(object):
    def trimBST(self, root, L, R):
        """
        :type root: TreeNode
        :type L: int
        :type R: int
        :rtype: TreeNode
        """
        if not root:
            return None
        if root.val < L:
            return self.trimBST(root.right, L, R)
        if root.val > R:
            return self.trimBST(root.left, L, R)
        root.left = self.trimBST(root.left, L, R)
        root.right = self.trimBST(root.right, L, R)
        return root

def up_adjust(arr):
    tmp = arr[-1]
    child_idx, parent_idx = len(arr) - 1, (len(arr) - 1 - 1) // 2

    while child_idx > 0 and tmp < arr[parent_idx]:
        arr[child_idx] = arr[parent_idx]
        child_idx, parent_idx = parent_idx, (parent_idx - 1) // 2
    arr[child_idx] = tmp


def down_adjust(parent_idx, length, arr):
    tmp = arr[parent_idx]
    child_idx = 2 * parent_idx + 1
    while child_idx < length:
        # 如果有右孩子，并且右孩子更小，则定位到右孩子
        if child_idx + 1 < length and arr[child_idx + 1] < arr[child_idx]:
            child_idx += 1

        # 如果已达到目的，则跳出
        if tmp <= arr[child_idx]:
            break

        arr[parent_idx] = arr[child_idx]
        parent_idx, child_idx = child_idx, 2 * child_idx + 1

    arr[parent_idx] = tmp


def build_heap(arr):
    for i in range((len(arr) - 1 - 1) // 2, -1, -1):
        down_adjust(i, len(arr), arr)


def pop_top(arr):
    if len(arr) == 1:
        return arr.pop()
    tmp = arr[0]
    arr[0] = arr.pop()
    down_adjust(parent_idx=0, length=len(arr), arr=arr)
    return tmp


class PriorityQueue:
    def __init__(self, arr):
        self.arr = arr

    def heapify(self):
        build_heap(self.arr)

    def heappop(self):
        return pop_top(self.arr)

    def heappush(self, val):
        self.arr.append(val)
        up_adjust(self.arr)

    def to_array(self):
        res = []
        while self.arr:
            res.append(self.heappop())
        return res


# %% 测试核心算法
arr = [1, 3, 2, 6, 5, 7, 8, 9, 0]
up_adjust(arr)
print(arr)

arr = [9, 3, 2, 6, 5, 7, 8]
down_adjust(parent_idx=0, length=len(arr), arr=arr)
print(arr)

arr = [7, 1, 3, 10, 5, 2, 8, 9, 6]
build_heap(arr)
print(arr)

# %%测试优先队列
arr = [9, 3, 2, 6, 5, 7, 8]
priority = PriorityQueue(arr)
priority.heapify()

priority.to_array()

import heapq

heap = [6, 5, 3, 1, 2, 0]
heapq.heapify(heap) # 把 heap 变为 heapq 格式的 list，时间复杂度为O(n)，直接修改 heap

heapq.heappush(heap, item) # 插入一个新值，直接修改 heap
heapq.heappop(heap) # 返回并删除最小的值（也就是树最顶端的值）

heapq.heappushpop(heap, item)
# 相当于heappush+heappop(但速度更快)
heapq.heapreplace(heap, item)
# 相当于heappop+相当于heappush(但速度更快)


heapq.nlargest(n=3, iterable=heap)
# 返回一个 list，从大到小排序，长度最多为 n，如果不够就能返回多少返回多少
heapq.nsmallest(n=3, iterable=heap)
# 返回一个 list，从小到大排序，长度最多为 n，如果不够就能返回多少返回多少

[heapq.heappop(heap) for i in range(len(heap))] # 等价于 sorted

heap=[]
for i in [4,3,2,5,6]:
    heapq.heappush(heap,[1,i]) # 注意到list和str也可以比大小，所以 item 可以是 list, str

import math
from io import StringIO


def show_tree(tree, total_width=36, fill=' '):
    output = StringIO()
    last_row = -1
    for i, n in enumerate(tree):
        if i:
            row = int(math.floor(math.log(i + 1, 2)))
        else:
            row = 0
        if row != last_row:
            output.write('\n')
        columns = 2 ** row
        col_width = int(math.floor((total_width * 1.0) / columns))
        output.write(str(n).center(col_width, fill))
        last_row = row
    print(output.getvalue())
    print('-' * total_width)

import random
import heapq

heap = list(range(1, 8))
random.shuffle(heap)
show_tree(heap)

heapq.heapify(heap)
show_tree(heap)

import heapq
import random

heap = []
data = list(range(1, 8))
random.shuffle(data)
print('data:', data)
for i in data:
    heapq.heappush(heap, i)
    show_tree(heap)

import heapq
import random

data = list(range(1, 8))
random.shuffle(heap)
print('data: ', heap)
heapq.heapify(heap)
show_tree(heap)

res = []
while data:
    i = heapq.heappop(data)
    print('pop %3d:' % i)
    show_tree(data)
    res.append(i)
print('heap: ', res)

class TrieNode:
    def __init__(self):
        self.children = dict()
        self.is_word = False


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        curr = self.root
        for char in word:
            if char not in curr.children:
                curr.children[char] = TrieNode()
            curr = curr.children[char]
        curr.is_word = True

    def search(self, word: str) -> bool:
        curr, idx = self.root, 0
        while curr.children.values() and idx < len(word):
            if word[idx] in curr.children:
                curr = curr.children[word[idx]]
            else:
                return False
            idx += 1

        if idx < len(word):
            return False
        return curr.is_word  # idx==len(word)

    def startsWith(self, prefix: str) -> bool:
        curr, idx = self.root, 0
        while curr.children.values() and idx < len(prefix):
            if prefix[idx] in curr.children:
                curr = curr.children[prefix[idx]]
            else:
                return False
            idx += 1

        if idx < len(prefix):
            return False
        return True

import collections


class TrieNode:
    def __init__(self):
        # 如果字符是有限的，这里可以用 list 来存储，然后使用 char - 'a' 来索引。
        # list 存储因为不需要做 Hash，因此更快，但内存消耗更大。
        # 这里使用 HashMap 来实现的
        self.children = collections.defaultdict(TrieNode)
        self.is_word = False


class Trie:

    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        curr = self.root
        for char in word:
            curr = curr.children[char]
        curr.is_word = True

    def remove(self, word: str) -> bool:
      # 删除前，需要用 match 查询是否存在此 word 
        raise PermissionError("从 trie 删除 keyword，还没有实现")

    def get_keywords(self):
        # 获取 keyword
        res = []

        def dfs(node, word):
            if node.is_word:
                res.append(word)

            for char in node.children:
                dfs(node.children[char], word + char)

        dfs(self.root, '')
        return res

    # 精确全文匹配
    def match(self, word: str) -> bool:
        curr = self.root
        for char in word:
            curr = curr.children.get(char)
            if curr is None:
                return False
        return curr.is_word

    def starts_with(self, prefix: str) -> bool:
        # 判断：prefix 是某个 keyword 的开头
        curr = self.root
        for char in prefix:
            curr = curr.children.get(char)
            if curr is None:
                return False
        return True

    def match_start(self, sentence) -> bool:
        # 判断：sentence 的开头是否是某个 keyword
        curr = self.root
        for char in sentence:
            if char not in curr.children:
                return False
            curr = curr.children.get(char)
            if curr.is_word:
                return True
        return False  # 理论上不会执行


trie = Trie()
trie.insert("apple")

assert trie.match("apple")
assert not trie.match("app")

assert trie.starts_with("app")
assert not trie.match_start("app is good")

trie.insert("app")
assert trie.match("app")

trie.get_keywords()

class Trie:

    def __init__(self):
        self.root = {}

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            node = node.setdefault(char, {})
        node['-'] = True

    def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            if char not in node:
                return False
            node = node[char]
        return '-' in node

    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for char in prefix:
            if char not in node:
                return False
            node = node[char]
        return True

    def in_start(self, sentence):
        node = self.root
        for char in sentence:
            if char not in node:
                return False
            node = node[char]
            if '-' in node:
                return True
        return True

1. return specific value for null node
2. update the answer if needed                      // anwer <-- params
3. left_ans = top_down(root.left, left_params)      // left_params <-- root.val, params
4. right_ans = top_down(root.right, right_params)   // right_params <-- root.val, params
5. return the answer if needed                      // answer <-- left_ans, right_ans

1. return specific value for null node
2. left_ans = bottom_up(root.left)          // call function recursively for left child
3. right_ans = bottom_up(root.right)        // call function recursively for right child
4. return answers                           // answer <-- left_ans, right_ans, root.val

1. return if root is null
2. if root is a leaf node:
3.      answer = max(answer, depth)         // update the answer if needed
4. maximum_depth(root.left, depth + 1)      // call the function recursively for left child
5. maximum_depth(root.right, depth + 1)     // call the function recursively for right child

1. return 0 if root is null                 // return 0 for null node
2. left_depth = maximum_depth(root.left)
3. right_depth = maximum_depth(root.right)
4. return max(left_depth, right_depth) + 1  // return depth of the subtree rooted at root


class Solution:
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        return 0 if root is None else max(self.maxDepth(root.left),self.maxDepth(root.right))+1

class Solution:
    # @param root, a tree link node
    # @return nothing
    def connect(self, root):
        if not root:return
        import collections
        deque = collections.deque([(root, 0)])
        output = dict()
        while deque:
            tmp_root, level = deque.popleft()
            if tmp_root.left: deque.append((tmp_root.left, level + 1))
            if tmp_root.right: deque.append((tmp_root.right, level + 1))
            if level in output:
                output[level].next = tmp_root
            output[level] = tmp_root

# merge
# Given two binary trees and imagine that when you put one of them to cover the other,
# some nodes of the two trees are overlapped while the others are not.
# merge them into a new binary tree.
# The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node.
# Otherwise, the NOT null node will be used as the node of new tree.
#
# Example :
# Input:
# 	Tree 1                     Tree 2
#           1                         2
#          / \                       / \
#         3   2                     1   3
#        /                           \   \
#       5                             4   7
# Output:
# Merged tree:
# 	     3
# 	    / \
# 	   4   5
# 	  / \   \
# 	 5   4   7

def mergeTrees(t1, t2):
    """
    :type t1: TreeNode
    :type t2: TreeNode
    :rtype: TreeNode
    """
    if (t1.val is not None) and (t2.val is not None):
        root = TreeNode(t1.val + t2.val)
        root.left = mergeTrees(t1.left, t2.left)
        root.right = mergeTrees(t1.right, t2.right)
        return root
    else:
        return t1 or t2

t1=list2tree(i=1,list_num=[1,2,3,4,None,None,5])
t2=list2tree(i=1,list_num=[2,9,None,None,3,None,None])

a=mergeTrees(t1, t2)

# 先子节点，后兄弟节点”的表示法
class Tree:
    def __init__(self, kids, next=None):
        self.kids = self.val = kids
        self.next = next