二叉树的遍历

from typing import List
import collections
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

root = TreeNode(1)

root.left = TreeNode(2)
root.left.left = TreeNode(3)
root.left.right = TreeNode(4)

root.right = TreeNode(5)
root.right.left = TreeNode(6)

class Solution:
    def preorderTraversalRecursion(self, root: TreeNode) -> List[int]:
        def preorder(root):
            if not root: return  
            res.append(root.val) ## 根节点
            preorder(root.left)  ## 左子树
            preorder(root.right) ## 右子树
            return res
        res = []
        preorder(root)
        return res

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if root is None: return []
        stack, res = [root], []
        while stack:
            node = stack.pop()
            res.append(node.val) ## 将"根"节点加入到结果中
            if node.right:       ## 先将右子树压入栈
                stack.append(node.right)
            if node.left:        ## 后将左子树压入栈
                stack.append(node.left)
        return res

mat = Solution()
print("\n前序输出：")
print(mat.preorderTraversal(root)) # [1, 2, 3, 4, 5, 6]
print(mat.preorderTraversalRecursion(root)) # [1, 2, 3, 4, 5, 6]

root = TreeNode(4)

root.left = TreeNode(2)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)

root.right = TreeNode(6)
root.right.left = TreeNode(5)

class Solution:
    def inorderTraversalRecursion(self, root: TreeNode) -> List[int]:
        def inorder(root):
            if not root: return
            inorder(root.left)   ## 左子树
            res.append(root.val) ## 根节点
            inorder(root.right)  ## 右子树
            return res
        res = []
        inorder(root)
        return res

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root: return []
        cur, stack, res = root, [], []
        while stack or cur:
            while cur:
                stack.append(cur)
                cur = cur.left
            node = stack.pop()
            res.append(node.val)
            cur = node.right
        return res

print("\n中序输出：")
print(mat.inorderTraversal(root)) # [1,2,3,4,5,6]
print(mat.inorderTraversalRecursion(root)) # [1,2,3,4,5,6]

class Solution:
    def postorderTraversalRecursion(self, root: TreeNode) -> List[int]:
        def postorder(root):
            if not root: return
            postorder(root.left)
            postorder(root.right)
            res.append(root.val)  ## 后序
            return res
        res = []
        postorder(root)
        return res

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        if root is None: return []
        stack, res = [(0, root)], []
        while stack:
            flag, node = stack.pop()
            if flag == 1 or (not (node.left or node.right)):
                res.append(node.val)
            else:
                stack.append((1, node))
                if node.right:
                    stack.append((0, node.right))
                if node.left:
                    stack.append((0, node.left))
        return res

class Solution:
    def levelTraversalLeft(self, root: TreeNode) -> List[List[int]]:
        if not root: return []
        from collections import deque
        res, queue = [], deque()
        queue.append(root)
        while queue:
            n, level = len(queue), []
            for _ in range(n):
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            res.append(level)
        return res

class Solution:
    def levelTraversalRight(self, root: TreeNode) -> List[List[int]]:
        if not root: return []
        res, queue = [], collections.deque()
        queue.append(root)
        while queue:
            n, level = len(queue), []
            for _ in range(n):
                node = queue.popleft()
                level.append(node.val)
                if node.right:
                    queue.append(node.right)
                if node.left:
                    queue.append(node.left)
            res.append(level)
        return res

class Solution:
    def levelTraversal(self, root: TreeNode) -> List[List[int]]:
        if not root: return []
        res, queue = [], collections.deque()
        queue.append(root)
        while queue:
            n, level = len(queue), collections.deque()
            for _ in range(n):
                node = queue.popleft()
                level.appendleft(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            res.append(list(level))
        return res

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root: return []
        from collections import deque
        k, res, queue = 1, [], deque()
        queue.append(root)
        while queue:
            n, level = len(queue), deque()
            k *= -1
            for _ in range(n):
                node = queue.popleft()
                if k == -1: ## 左 --> 右
                    level.append(node.val)
                else:       ## 右 --> 左
                    level.appendleft(node.val)
                if node.left: queue.append(node.left)
                if node.right:queue.append(node.right)
            res.append(list(level))
        return res

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        def bottomUp(root):         ## 自下而上
            return 0 if not root else max(bottomUp(root.left), bottomUp(root.right)) + 1
        def topDown(root, depth=0): ## 自上而下
            return depth if not root else max(topDown(root.left, depth+1), topDown(root.right, depth+1))
        return topDown(root), bottomUp(root)