二叉树遍历总结

二叉树的前序遍历

递归

# 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
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        #递归
        self.res = []
        def preorder(root):
            if not root: return
            self.res.append(root.val)
            preorder(root.left)
            preorder(root.right)
        preorder(root)
        return self.res

迭代

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

二叉树的中序遍历

递归

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        #递归
        res = []
        def recur(root):
            if not root: return
            if root.left: recur(root.left)
            res.append(root.val)
            if root.right: recur(root.right)
        recur(root)
        return res

迭代

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        #迭代
        if not root: return []
        stack, res = [root], []
        visited = set()
        visited.add(root)
        while stack:
            p = stack[-1]
            while p.left and p.left not in visited:
                visited.add(p.left)
                stack.append(p.left)
                p = p.left
            p = stack.pop()
            res.append(p.val)
            if p.right: stack.append(p.right)
        return res

二叉树的后序遍历

递归

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

迭代

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        #迭代
        res, stack = [], []
        p, pre = root, None
        while True:
            if p:
                stack.append(p)
                p = p.left
            elif stack:
                p = stack.pop()
                if not p.right or pre == p.right:
                    res.append(p.val)
                    pre, p = p, None
                else:
                    stack.append(p)
                    p = p.right
            else:
                break
        return res

层序

递归

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        #递归
        if not root: return []
        res = []
        def dfs(index, root):
            if len(res) < index:
                res.append([])
            res[index-1].append(root.val)
            if root.left: dfs(index+1, root.left)
            if root.right: dfs(index+1, root.right)
        dfs(1, root)
        return res

迭代

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        #迭代
        if not root: return []
        queue, res = [root], []
        while queue:
            tmp = []
            for _ in range(len(queue)):
                p = queue.pop(0)
                tmp.append(p.val)
                if p.left: queue.append(p.left)
                if p.right: queue.append(p.right)
            res.append(tmp)
        return res