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

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

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

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

迭代版本

##### 非递归方式实现（循环+队列） #######
# 先序
def preOrder(root):if root == None:                 # 重点，千万不要忘记写了，否则遇到叶子节点无法再接着遍历下去return NonetmpNode = rootstack = []while tmpNode or stack:while tmpNode:print(tmpNode.val)stack.append(tmpNode)tmpNode = tmpNode.leftnode = stack.pop()if node.right:tmpNode = node.right# 中序
def midOrder(root):if root == None:                 # 重点，千万不要忘记写了，否则遇到叶子节点无法再接着遍历下去return NonetmpNode = rootstack = []while tmpNode or stack:while tmpNode:#print(tmpNode.val)stack.append(tmpNode)tmpNode = tmpNode.leftnode = 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 NonetmpNode = rootstack = []while tmpNode or stack:while tmpNode:stack.append(tmpNode)tmpNode = tmpNode.leftnode = stack[-1]tmpNode =node.rightif 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 = Nonewhile root or stack:while root:stack.append(root)root = root.leftroot = stack.pop()if not root.right or prev == root.right:res.append(root.val)prev = rootroot = Noneelse:stack.append(root)root = root.rightreturn 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