二叉树

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

    def __repr__(self) -> str:
        return str(self.val)

class BinaryTree:
    def __init__(self, root=None) -> None:
        self.root = root

    def __iter__(self):
        if not self.root:
            return
        que = [self.root]
        while que:
            node = que.pop(0)
            yield node.val
            if node.left:
                que.append(node.left)
            if node.right:
                que.append(node.right)

    def __len__(self):
        return self.size

    def __str__(self) -> str:
        pass

    @property
    def size(self):
        def size_recur(root):
            if not root:
                return 0
            return 1 + size_recur(root.left) + size_recur(root.right)
        return size_recur(self.root)

    @property
    def height(self):
        def height_recur(root):
            if not root:
                return 0
            left_height = height_recur(root.left)
            right_height = height_recur(root.right)
            return max(left_height, right_height) + 1
        return height_recur(self.root)

    @property
    def is_complete(self):
        pass

    @property
    def is_balanced(self):
        pass

    @property
    def is_bst(self):
        pass

    @property
    def is_symmetric(self):
        pass

    def equals(self, other):
        pass

    def print(self):
        pass

    def dfs(self, order='pre', recur=False):
        def preorder(root):
            stack = [root]
            while stack:
                node = stack.pop()
                if node:
                    yield node.val
                    stack.append(node.right)
                    stack.append(node.left)
        def inorder(root):
            stack = []
            while stack or root:
                while root:
                    stack.append(root)
                    root = root.left
                root = stack.pop()
                yield root.val
                root = root.right
        def postorder(root):
            # 创建一个空列表，用于存储已经访问的节点
            visited_nodes = []
            stack = [root]

            while stack:
                current_node = stack.pop()
                visited_nodes.append(current_node)

                # 按照从左到右的顺序处理左右子节点
                if current_node.left:
                    stack.append(current_node.left)

                if current_node.right:
                    stack.append(current_node.right)

            # 将 visited_nodes 列表中的节点按照后序遍历的顺序输出
            while visited_nodes:
                yield visited_nodes.pop().val
        def preorder_recur(root):
            if root:
                yield root.val
                yield from preorder_recur(root.left)
                yield from preorder_recur(root.right)
        def inorder_recur(root):
            if root:
                yield from inorder_recur(root.left)
                yield root.val
                yield from inorder_recur(root.right)
        def postorder_recur(root):
            if root:
                yield from postorder_recur(root.left)
                yield from postorder_recur(root.right)
                yield root.val

        root = self.root
        if recur:
            match order:
                case 'pre': return preorder_recur(root)
                case 'in': return inorder_recur(root)
                case 'post': return postorder_recur(root)
        else:
            match order:
                case 'pre': return preorder(root)
                case 'in': return inorder(root)
                case 'post': return postorder(root)

    def bfs(self):
        if not self.root:
            return []
        que = [self.root]
        res = []
        while que:
            level = []
            for _ in range(len(que)):
                node = que.pop(0)
                level.append(node.val)
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
            res.append(level)
        return res

    def morris_traverse(self):
        pass

    def serialize(self):
        def _serialize(root):
            if root is None:
                return '#'
            left = _serialize(root.left)
            right = _serialize(root.right)
            return ','.join([str(root.val), left, right])
        return _serialize(self.root)

    @staticmethod
    def deserialize(s):
        lst = s.split(',') if isinstance(s, str) else s
        return BinaryTree.build_tree(lst)

    @staticmethod
    def build_tree(lst):
        val = lst.pop(0)
        if val in (None, '#'):
            return None
        else:
            node = TreeNode(val)
            node.left = BinaryTree.build_tree(lst)
            node.right = BinaryTree.build_tree(lst)
            return node

    def add(self, val):
        def add_recur(root, val):
            if not root:
                root = TreeNode(val)
            elif val < root.val:
                root.left = add_recur(root.left, val)
            elif val > root.val:
                root.right = add_recur(root.right, val)
            return root

        self.root = add_recur(self.root, val)

    def remove(self, val):
        pass

    def search(self, val):
        pass