代码随想录算法训练营第十三天| 144、二叉树的前序遍历 125、二叉树的后序遍历 94、二叉树的中序遍历 102、二叉树的层序遍历

目录二叉树理论基础1. 分类1. 满二叉树2.完全二叉树3.二叉搜索树4.平衡二叉搜索树2.二叉树的存储方式3.二叉树的遍历方法4.二叉树的定义二叉树的递归遍历递归三部曲144. 二叉树的前序遍历题目描述题解145. 二叉树的后序遍历题目描述题解94. 二叉树的中序遍历题目描述题解二叉树的迭代遍历144. 二叉树的前序遍历解题思路145. 二叉树的后序遍历解题思路102. 二叉树的层序遍历题目描述解题思路二叉树理论基础1. 分类1. 满二叉树一颗二叉树只有度为0的结点和度为2的结点并且度为0的结点在一层2.完全二叉树前k-1层全部结点都存在第k层前n个都存在3.二叉搜索树二叉搜索树是一个有序树若它的左子树不空则左子树上所有结点的值均小于它的根结点的值若它的右子树不空则右子树上所有结点的值均大于它的根结点的值它的左、右子树也分别为二叉排序树4.平衡二叉搜索树AVL(Adelson-Velsky and Landis)性质是一个空树或者他的左右两个子树高度差绝对值不超过1并且左右两个子树都是一颗平衡二叉树2.二叉树的存储方式顺序存储数组链式存储指针3.二叉树的遍历方法深度优先遍历先往深走遇到叶子节点再往回走广度优先遍历一层一层遍历(5471278)4.二叉树的定义class TreeNode: def __init__(self,val 0,left None,right None): self.val val self.left left self.right right二叉树的递归遍历递归三部曲确定递归函数的参数和返回值确定终止条件确定单层递归的逻辑144. 二叉树的前序遍历题目描述给你二叉树的根节点root返回它节点值的前序遍历。题解class Solution: def preorderTraversal(self, root: Optional[TreeNode]) - List[int]: vec [] def dfs(node): if node is None: return vec.append(node.val) dfs(node.left) dfs(node.right) dfs(root) return vec145. 二叉树的后序遍历题目描述给你一棵二叉树的根节点root返回其节点值的后序遍历。题解class Solution: def postorderTraversal(self, root: Optional[TreeNode]) - List[int]: vec [] def dfs(node): if node is None: return dfs(node.left) dfs(node.right) vec.append(node.val) dfs(root) return vec94. 二叉树的中序遍历题目描述给定一个二叉树的根节点root返回它的中序遍历。题解class Solution: def inorderTraversal(self, root: Optional[TreeNode]) - List[int]: vec [] def dfs(node): if node is None: return dfs(node.left) vec.append(node.val) dfs(node.right) dfs(root) return vec二叉树的迭代遍历144. 二叉树的前序遍历解题思路模拟存到栈中时先存左节点再存右节点因为栈是先进后出pop时会先popleft时间复杂度O(n)空间复杂度O(n)class Solution: def preorderTraversal(self, root: Optional[TreeNode]) - List[int]: stack [] stack.append(root) res [] while stack and root: node stack.pop() if node is not None: res.append(node.val) else: continue stack.append(node.right) stack.append(node.left) return res145. 二叉树的后序遍历解题思路后序遍历是左右中前序遍历是中左右那么如果对前序遍历的代码进行调整变成中右左存储数组中再对数组进行反转即可得到后序遍历class Solution: def postorderTraversal(self, root: Optional[TreeNode]) - List[int]: stack [] res [] stack.append(root) while stack and root: node stack.pop() if node: res.append(node.val) else: continue stack.append(node.left) stack.append(node.right) return res[::-1]102. 二叉树的层序遍历题目描述给你二叉树的根节点root返回其节点值的层序遍历。 即逐层地从左到右访问所有节点。解题思路模拟class Solution: def levelOrder(self, root: Optional[TreeNode]) - List[List[int]]: queue deque([root]) res [] if not root: return res while queue: size len(queue) level [] for _ in range(size): node queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) res.append(level) return res