# 两种写法 
# 时间复杂度低 且考虑特殊情况
class Solution:
    def isPalindrome(self, x: int) -> bool:
        # first solution follow the answer
        if x < 0 or ( x % 10 == 0 and x != 0 ):
            return False
         
        revertedNumber = 0
        while x > revertedNumber:
            revertedNumber = revertedNumber * 10 + x % 10
            x //= 10
        return x == revertedNumber or x == revertedNumber // 10

# 直接暴力结束 且不用考虑情况
def isPalindrome(self, x: int) -> bool:
        return str(x) == str(x)[::-1]

# 1 钻入死胡同
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if root == None: return []
        rst, stack = [] , []
        stack.append(root)
        stack_1 = []
        while stack:
            ele = []
            while stack:
                cur = stack.pop()
                if isinstance(cur, TreeNode):
                    stack_1.extend([cur.right, cur.left])
                else:
                    stack.pop()
                    continue
                ele.append(cur.val)
            if ele: rst.append(ele)
            ele = []
            while stack_1:
                cur = stack_1.pop()
                if isinstance(cur, TreeNode):
                    stack.extend([cur.right, cur.left])
                else:
                    stack_1.pop()
                    continue
                ele.append(cur.val)
            if ele: rst.append(ele)
        return rst

# 2 清醒 
# 欣赏一个老哥子的代码 时空复杂度均为O(n)
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        ans = []
        # 创建 stack 完成 root 加载 if root == None 则加载 []
        stack = [root] if root else []
        while stack:
            # 循环内部创建tmp栈
            tmp_stack = []
            # 使用推导式直接append所有val节省打字实践
            ans.append([i.val for i in stack])
            # 顺序读 伪栈 直接 append (node.left) (node.right)
            for node in stack:
                if node.left:
                    tmp_stack.append(node.left)
                if node.right:
                    tmp_stack.append(node.right)
            # 每次完成 首先更新ans 然后更新外部栈
            stack = tmp_stack
        return ans

# 这不就层序遍历...
# 在层序遍历的代码中加入maxSize 这样可以直接返回最大深度
# 使用 bfs
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        maxSize = 0
        stack = [root] if root else []
        while stack:
            tmp_stack = []
            for node in stack:
                if node.left:
                    tmp_stack.append(node.left)
                if node.right:
                    tmp_stack.append(node.right)
            stack = tmp_stack
            maxSize += 1
        return maxSize
# 非常 easy


# 使用 dfs
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root is None: return 0
        else:
            return max(self.maxDepth(root.left),self.maxDepth(root.right)) + 1
# 虽然很快 但是递归需要使用栈空间 
# 时间复杂度为O(n) 空间复杂度为O(height)依据树的高度而定

# 思路： preorder开头卡一刀 拿root
# inroder中间卡一刀 拿两边的inorder 用两边的inorder来分割preorder的后面部分
# preorder再卡一刀 拆成两个sub-inorder 的 sub-preorder 做成递归形态 返回

# 官方题解讲的太清楚 导致我一点都不想看
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        # judge 
        if preorder == [] and inorder == []:
            return
        root = TreeNode(preorder[0])
        i = inorder.index(preorder[0])
        root.left = self.buildTree(preorder[1:i+1],inorder[:i])
        root.right = self.buildTree(preorder[i+1:],inorder[i+1:])
        return root
# 递归栈导致内存消耗过大
# 明天使用stack遍历序列重写