求职刷题力扣DAY14 ---二叉树的基础遍历，迭代、递归

各种python遍历集合**：94. 二叉树的中序遍历 - 力扣（LeetCode）

# 前序遍历
def dfs(root):
	if not root:return
	dfs(root.left)
	res.append(root.val)
	dfs(root.right)

前、中、后： 根左右、 左根右、 左右根。

迭代版本

##### 非递归方式实现（循环+队列） #######
# 先序
def preOrder(root):
    if root == None:                 # 重点，千万不要忘记写了，否则遇到叶子节点无法再接着遍历下去
        return None
    tmpNode = root
    stack = []

    while tmpNode or stack:
        while tmpNode:
            print(tmpNode.val)
            stack.append(tmpNode)
            tmpNode = tmpNode.left
        node = stack.pop()
        if node.right:
            tmpNode = node.right

# 中序
def midOrder(root):
    if root == None:                 # 重点，千万不要忘记写了，否则遇到叶子节点无法再接着遍历下去
        return None
    tmpNode = root
    stack = []

    while tmpNode or stack:
        while tmpNode:
            #print(tmpNode.val)
            stack.append(tmpNode)
            tmpNode = tmpNode.left
        node = stack.pop()
        print(node.val)
        if node.right:
            tmpNode = node.right

# 后序(难,背下来)
# 思路：
# 遍历依旧是先遍历左边到最深，再遍历右边，遍历完了右边才pop根节点
# 需要注意的是：当右节点为空时，才pop根节点，而且pop了根节点后需要继续判断pop的节点是不是上一个节点的右节点，是的话还要继续pop上一节点
# 打印的时候，相当于最后打印根节点，根节点是栈里最后pop出的，所以在pop的时候打印即可
def latterOrder(root):
    if root == None:                 # 重点，千万不要忘记写了，否则遇到叶子节点无法再接着遍历下去
        return None
    tmpNode = root
    stack = []

    while tmpNode or stack:
        while tmpNode:
            stack.append(tmpNode)
            tmpNode = tmpNode.left
        node = stack[-1]
        tmpNode =node.right

        if node.right == None:
            node = stack.pop()
            print(node.val)
            while stack and node == stack[-1].right:
                node = stack.pop()
                print(node.val)
                
//
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        #前序遍历，根右左再颠倒一下即可
        res = []
        stack = []
        prev = None
        while root or stack:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            if not root.right or prev == root.right:
                res.append(root.val)
                prev = root
                root = None
            else:
                stack.append(root)
                root = root.right
        return res

1.2 层序遍历

102. 二叉树的层序遍历 - 力扣（LeetCode）

python 使用collections.deque进行实现，队列。

当queue不为空的时候进行while循环，循环体内部使用for 循环对每层进行循环：

for _ in range(len(queue))

循环中，一边将当前节点的值加入tmp中，一边将当前节点的左右子节点（不为空的话加入到queue中）

一层循环结束，将tmp加入的最后res结果之中。

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
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:return []
        queue = collections.deque()
        queue.append(root)
        res = []
        while queue:
            tmp = []
            for _ in range(len(queue)):
                cur = queue.popleft()
                tmp.append(cur.val)
                if cur.left:queue.append(cur.left)
                if cur.right:queue.append(cur.right)
            res.append(tmp)
        return res