二叉树算法解析：从基础遍历到高频面试题

1. 二叉树算法题与选择题解析二叉树是数据结构中最基础也是最重要的非线性结构之一在算法面试和笔试中出现的频率极高。掌握二叉树的各种操作和特性是每个程序员必备的基本功。本文将系统性地梳理二叉树相关的算法题和选择题帮助读者全面掌握这一数据结构。2. 二叉树基础概念2.1 二叉树定义与分类二叉树Binary Tree是n(n≥0)个结点的有限集合该集合或者为空集称为空二叉树或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。常见的二叉树类型包括满二叉树所有非叶子节点都有两个子节点且所有叶子节点都在同一层完全二叉树除最后一层外其他各层的节点数都达到最大个数且最后一层的节点都连续集中在最左边二叉搜索树(BST)左子树所有节点的值小于根节点右子树所有节点的值大于根节点平衡二叉树(AVL树)任何节点的左右子树高度差不超过12.2 二叉树存储方式二叉树主要有两种存储方式链式存储通过节点对象存储每个节点包含数据域和左右指针域顺序存储使用数组存储对于下标为i的节点其左子节点下标为2i1右子节点为2i23. 二叉树遍历算法3.1 深度优先遍历(DFS)深度优先遍历有三种主要方式前序遍历根→左→右中序遍历左→根→右后序遍历左→右→根递归实现示例Pythondef preorder(root): if not root: return print(root.val) # 访问根节点 preorder(root.left) # 遍历左子树 preorder(root.right) # 遍历右子树非递归实现通常使用栈来模拟递归过程def inorder(root): stack [] while stack or root: while root: stack.append(root) root root.left root stack.pop() print(root.val) root root.right3.2 广度优先遍历(BFS)广度优先遍历又称层次遍历使用队列实现from collections import deque def levelOrder(root): if not root: return [] queue deque([root]) res [] while queue: node queue.popleft() res.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) return res4. 经典二叉树算法题4.1 二叉树的最大深度问题描述给定二叉树根节点返回其最大深度。解法def maxDepth(root): if not root: return 0 return max(maxDepth(root.left), maxDepth(root.right)) 14.2 验证二叉搜索树问题描述判断二叉树是否是有效的二叉搜索树。解法def isValidBST(root): stack, prev [], float(-inf) while stack or root: while root: stack.append(root) root root.left root stack.pop() if root.val prev: return False prev root.val root root.right return True4.3 二叉树的最近公共祖先问题描述找到二叉树中两个节点的最近公共祖先。解法def lowestCommonAncestor(root, p, q): if not root or root p or root q: return root left lowestCommonAncestor(root.left, p, q) right lowestCommonAncestor(root.right, p, q) if left and right: return root return left if left else right5. 二叉树选择题解析5.1 二叉树性质相关完全二叉树的节点数高度为h的完全二叉树最少有2^h个节点最多有2^(h1)-1个节点二叉搜索树的中序遍历结果是一个升序序列平衡二叉树的高度n个节点的平衡二叉树高度为O(logn)5.2 遍历序列相关已知前序和中序序列可以唯一确定一棵二叉树已知后序和中序序列可以唯一确定一棵二叉树已知前序和后序序列不能唯一确定二叉树除非是满二叉树6. 实战技巧与注意事项递归终止条件处理二叉树问题时必须明确递归的终止条件通常是if not root: return空间复杂度优化递归解法空间复杂度为O(h)h为树高非递归解法可以控制到O(1)边界条件处理特别注意空树、单节点树、左/右子树为空等特殊情况遍历顺序选择根据问题特点选择合适的遍历顺序如前序适合自上而下后序适合自下而上7. 高频面试题总结二叉树的前序/中序/后序遍历递归和非递归二叉树的层次遍历及其变种如锯齿形遍历二叉树的最大深度/最小深度平衡二叉树的判断对称二叉树的判断二叉搜索树的验证二叉搜索树中第K小的元素二叉树的最近公共祖先二叉树路径和问题二叉树的序列化与反序列化8. 性能优化建议记忆化递归对于重复计算的子树问题可以使用哈希表缓存结果Morris遍历实现O(1)空间复杂度的中序遍历迭代替代递归对于深度较大的树避免递归导致的栈溢出剪枝策略在搜索过程中及时排除不可能的分支掌握这些二叉树算法和选择题不仅能帮助你在面试中游刃有余更能提升解决实际工程问题的能力。建议读者动手实现每个算法理解其背后的思想而不仅仅是记住代码。