class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        stack = [root]
        ans = list()
        while stack:
            node = stack.pop()
            ans.append(node.val)
            # 先右后左，保证出栈时先遍历左子树
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return ans

class Solution:
    # 中序遍历为left -> root -> right
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        stack = list()
        ans = list()
        cur = root
        while cur or stack:
            while cur:
                stack.append(cur)
                cur = cur.left
            node = stack.pop()
            ans.append(node.val)
            cur = node.right
        return ans

class Solution:
    # 前序遍历为root->left->right，后序遍历为left->right->root。
    # 可以修改前序遍历成为 root -> right -> left，那么这个顺序就
    # 和后序遍历正好相反。
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        stack = [root]
        ans = list()
        while stack:
            node = stack.pop()
            ans.append(node.val)
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
        return ans[::-1]

class Solution:
    # 经典层次遍历问题，需要借助队列进行遍历节点的存取，
    def averageOfLevels(self, root: TreeNode) -> List[float]:
        # 定义队列，用于存取节点
        queue = [root]
        # ans用于存放
        ans = list()
        # 队列判空循环
        while queue:
            # 获取当前队列的长度
            length = len(queue)
            # 当前队列中节点的循环处理
            for _ in range(length):
                # 出队赋值给node
                node = queue.pop()
                # num的加法处理
                ans.append(node.val)
                # 判断出队节点的左子树是否为空，不为空则入队
                if node.left:
                    queue.insert(0, node.left)
                # 判断出队节点的右子树是否为空，不为空则入队
                if node.right:
                    queue.insert(0, node.right)
        # 返回结果列表
        return ans

class Solution:
    '''
    如果我们知道了左子树和右子树的最大深度l和r，那么该二叉树的
    最大深度即为max(l,r)+1,而左子树和右子树的最大深度又可以以
    同样的方式进行计算。因此我们可以用「深度优先搜索」的方法来
    计算二叉树的最大深度。具体而言，在计算当前二叉树的最大深度
    时，可以先递归计算出其左子树和右子树的最大深度，然后在O(1)
    时间内计算出当前二叉树的最大深度。递归在访问到空节点时退出。
    该方法的时间复杂度为O(N)，空间复杂度为O(height)。
    '''
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        r = self.maxDepth(root.right)
        l = self.maxDepth(root.left)
        return max(r,l) + 1