深度优先遍历dfs

前序遍历

递归

def preorderTraversal(root):
    res = []
    def traverse(root):
        if not root:
            return
        res.append(root.val)
        traverse(root.left)
        traverse(root.right)
       
    if not root:
        return res
    traverse(root)
    return res

迭代

def preorderTraverse(root):
    if not root:
        return []
    res = []
    stack = []
    while root or stack:
        while root:
            res.append(root.val)
            stack.append(root)
            root = root.left
        root = stack.pop()
        root = root.right
    return res

中序遍历

递归

def inorderTraversal(root):
    res = []
    def traverse(root):
        if not root:
            return
        traverse(root.left)
        res.append(root.val)
        traverse(root.right)
       
    if not root:
        return res
    traverse(root)
    return res

迭代

def inorderTraverse(root):
	if not root:
        return []
        
    stack = []
    res = []
    while root or stack:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        res.append(root.val)
        root = root.right
        
    return res

后序遍历

递归

def postorderTraversal(root):
    res = []
    def traverse(root):
        if not root:
            return
        traverse(root.left)
        traverse(root.right)
        res.append(root.val)
       
    if not root:
        return res
    traverse(root)
    return res

迭代

def postOrderTraverse(root):
    if not root:
        return []
    prev = None
    stack = []
    res = []
    while root or stack:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        if not root.right or root.right == prev:
            res.append(root.val)
            prev = root
            root = None
        else:
            stack.append(root)
            root = root.right
    return res

宽度优先遍历bfs

迭代

class TreeNode:
    def __init__(self,val=0,left=None,right=None):
        self.val = val
        self.left = left
        self.right = right
def levelOrder(root):
    
    if not root:
        return []
    q = collections.deque([root])
    res = []
    while q:
        sz = len(q)
        level = []
        for i in range(sz):
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        res.append(level)
    return res

递归

def levelOrder(root):
    if not root:
    return []
        
    def traverse(root,layer):
        if len(res) < layer:
            res.append([])
        if not root:
            return
        res[layer - 1].append(root.val)
        if root.left:
            traverse(root.left, layer + 1)
        if root.right:
            traverse(root.right, layer + 1)

    res = []
    traverse(root,1)
    return res

扩展

#根据前序和中序，输出后序
def lastorder(preorder, inorder):
    stack = []
    def helper(preStart, preEnd, inStart, inEnd):
        if preStart > preEnd or inStart > inEnd:
            return None
        #按根、右、左的顺序放入栈
        rootVal = preorder[preStart]
        stack.append(preorder[preStart])
        idx = 0
        for i in range(len(preorder)):
            if inorder[i] == rootVal:
                idx = i
                break
        right = helper(preStart + idx - inStart + 1, preEnd, idx + 1, inEnd)
        left = helper(preStart+1, preStart + idx - inStart, inStart, idx - 1)
    helper(0, len(preorder) - 1, 0, len(inorder) - 1)
    res = []
    while stack:
        res.append(stack.pop())
    return res