# ===== CodeLab: algo-tree =====
# 以下代码片段按文章出现顺序拼接, 共 6 段

# ----- 片段 1 (python) -----
from collections import deque

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

def build_tree(vals):
    """层序数组 -> 二叉树,None 表示空位"""
    if not vals or vals[0] is None:
        return None
    root = TreeNode(vals[0])
    q = deque([root])
    i = 1
    while i < len(vals):
        node = q.popleft()
        if vals[i] is not None:
            node.left = TreeNode(vals[i])
            q.append(node.left)
        i += 1
        if i < len(vals) and vals[i] is not None:
            node.right = TreeNode(vals[i])
            q.append(node.right)
        i += 1
    return root

# 树结构:
#       1
#      / \
#     2   3
#    / \   \
#   4   5   6
root = build_tree([1, 2, 3, 4, 5, None, 6])

# ----- 片段 2 (python) -----
def preorder(root):
    if root is None:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)

def inorder(root):
    if root is None:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

def postorder(root):
    if root is None:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]

root = build_tree([1, 2, 3, 4, 5, None, 6])
print(preorder(root))    # [1, 2, 4, 5, 3, 6]
print(inorder(root))     # [4, 2, 5, 1, 3, 6]
print(postorder(root))   # [4, 5, 2, 6, 3, 1]

# ----- 片段 3 (python) -----
def inorder_iter(root):
    res = []
    stack = []
    cur = root
    while cur or stack:
        while cur:            # 一路向左,入栈
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()     # 弹出,访问
        res.append(cur.val)
        cur = cur.right       # 转向右子树
    return res

root = build_tree([1, 2, 3, 4, 5, None, 6])
print(inorder_iter(root))    # [4, 2, 5, 1, 3, 6]

# ----- 片段 4 (python) -----
def level_order(root):
    if root is None:
        return []
    res = []
    q = deque([root])
    while q:
        level = []
        for _ in range(len(q)):   # 处理完整的一层
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        res.append(level)
    return res

root = build_tree([1, 2, 3, 4, 5, None, 6])
print(level_order(root))
# [[1], [2, 3], [4, 5, 6]]

# ----- 片段 5 (python) -----
def build_from_pre_in(preorder, inorder):
    if not preorder:
        return None
    val = preorder[0]
    idx = inorder.index(val)        # 根在中序中的位置
    root = TreeNode(val)
    root.left = build_from_pre_in(
        preorder[1:idx + 1], inorder[:idx])
    root.right = build_from_pre_in(
        preorder[idx + 1:], inorder[idx + 1:])
    return root

root = build_from_pre_in([1, 2, 4, 5, 3, 6], [4, 2, 5, 1, 3, 6])
print(preorder(root))    # [1, 2, 4, 5, 3, 6]
print(inorder(root))     # [4, 2, 5, 1, 3, 6]

# ----- 片段 6 (python) -----
def max_depth(root):
    if root is None:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

def is_symmetric(root):
    def check(a, b):
        if a is None and b is None:
            return True
        if a is None or b is None:
            return False
        return (a.val == b.val and
                check(a.left, b.right) and   # 镜像位置
                check(a.right, b.left))
    return check(root, root)

root = build_tree([1, 2, 2, 3, 4, 4, 3])
print(max_depth(root))        # 3
print(is_symmetric(root))     # True
root2 = build_tree([1, 2, 2, None, 3, None, 3])
print(is_symmetric(root2))    # False