二叉树的遍历（前序遍历，中序遍历，后序遍历，层序遍历）

144. 二叉树的前序遍历

给定一个二叉树，返回它的 前序 遍历。

示例:

输入: [1,null,2,3]
1

2
/
3

输出: [1,2,3]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？

递归

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        res=[]
        def helper(root):
            if not root :
                return 
            res.append(root.val)
            if root.left:
                helper(root.left)
            if root.right:
                helper(root.right)
        helper(root)
        return res
        

迭代

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

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

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

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

94. 二叉树的中序遍历

给定一个二叉树，返回它的中序 遍历。

示例:

输入: [1,null,2,3]
1

2
/
3

输出: [1,3,2]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？

递归

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

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

迭代

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

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

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

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

145. 二叉树的后序遍历

给定一个二叉树，返回它的 后序 遍历。

示例:

输入: [1,null,2,3]
1

2
/
3

输出: [3,2,1]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？

递归

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

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

迭代

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

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

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

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

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

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

102. 二叉树的层序遍历

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

示例：
二叉树：[3,9,20,null,null,15,7],

3

/
9 20
/
15 7
返回其层次遍历结果：

[
[3],
[9,20],
[15,7]
]
通过次数111,934提交次数181,382
在真实的面试中遇到过这道题？

递归

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        res=[]
        def helper (root,depth):
            if not root:
                return 
            if len(res)<=depth:
                res.append([])
            res[depth].append(root.val)
            helper(root.left,depth+1)
            helper(root.right,depth+1)
        helper(root,0)
        return res

迭代

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        res=[]
        queue=[root]
        while queue:
            temp1=queue[:]
            queue=[]
            
            temp2=[]
            while temp1:
                cur=temp1.pop(0)
                if not cur:
                    continue 
                temp2.append(cur.val)
                queue.append(cur.left)
                queue.append(cur.right)
            if temp2:
                res.append(temp2)
        return res

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if root is None:
            return []
        q = [root]
        result = []
        while q:
            res=[]
            for i in range(len(q)):
                cur=q.pop(0)
                res.append(cur.val)
                if cur.left:
                    q.append(cur.left)
                if cur.right:
                    q.append(cur.right)
            result.append(res)
        return result

有一点时间没刷数据结构的题了，感觉都有点生疏了，趁着假期的尾巴把二叉树的遍历整理一遍。感觉还不错。

转载：https://blog.csdn.net/weixin_45569785/article/details/105923695