1. 二叉树与二叉搜索树核心算法解析在数据结构与算法领域二叉树是最基础也是最重要的非线性数据结构之一。今天我将分享五个经典二叉树问题的完整解决方案这些算法题在技术面试中出现频率极高也是日常开发中处理树形数据的必备技能。无论你是准备面试还是提升编码能力这些内容都值得反复练习。2. 合并二叉树问题2.1 问题描述与递归解法给定两棵二叉树将它们合并为一棵新二叉树。合并规则是如果两个节点重叠将它们的值相加作为新节点的值否则不为空的节点将作为新树的节点。def mergeTrees(t1, t2): if not t1: return t2 if not t2: return t1 t1.val t2.val t1.left mergeTrees(t1.left, t2.left) t1.right mergeTrees(t1.right, t2.right) return t1关键点递归终止条件是任一树节点为空时返回另一树的节点。时间复杂度O(min(m,n))空间复杂度O(min(m,n))取决于递归深度。2.2 迭代解法与性能优化对于深度较大的树递归可能导致栈溢出。这时可以使用层序遍历的迭代解法from collections import deque def mergeTreesIterative(t1, t2): if not t1: return t2 queue deque([(t1, t2)]) while queue: n1, n2 queue.popleft() if not n2: continue n1.val n2.val if not n1.left: n1.left n2.left else: queue.append((n1.left, n2.left)) if not n1.right: n1.right n2.right else: queue.append((n1.right, n2.right)) return t13. 二叉搜索树中的搜索3.1 BST特性与搜索算法二叉搜索树(BST)具有左子树所有节点值小于根节点右子树所有节点值大于根节点的特性。利用这一特性可以实现高效搜索def searchBST(root, val): while root and root.val ! val: root root.left if val root.val else root.right return root3.2 递归与迭代实现对比递归实现更简洁但可能有栈溢出风险def searchBSTRecursive(root, val): if not root or root.val val: return root return searchBSTRecursive(root.left if val root.val else root.right, val)时间复杂度均为O(h)h为树高。平衡BST时为O(log n)最坏情况(链表状)O(n)。4. 二叉树的最近公共祖先4.1 LCA问题定义给定二叉树和两个节点p、q找到它们最近的共同祖先。最近公共祖先(LCA)是同时具有p、q作为后代的最低节点允许节点是自身的祖先。4.2 递归解法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 or right4.3 迭代解法与路径记录对于大规模树可以记录从根到p、q的路径然后比较路径def lowestCommonAncestorPath(root, p, q): def getPath(node, target): path, stack [], [] while True: while node: stack.append((node, False)) node node.left node, visited stack.pop() if visited: if node target: return path [node] path.pop() node None else: path.append(node) stack.append((node, True)) node node.right path_p getPath(root, p) path_q getPath(root, q) lca None for u, v in zip(path_p, path_q): if u v: lca u else: break return lca5. 删除二叉搜索树中的节点5.1 删除操作分类BST节点删除分三种情况无子节点直接删除有一个子节点用子节点替代有两个子节点用后继节点(右子树最左)或前驱节点(左子树最右)替代5.2 实现代码def deleteNode(root, key): if not root: return None if key root.val: root.left deleteNode(root.left, key) elif key root.val: root.right deleteNode(root.right, key) else: if not root.left: return root.right if not root.right: return root.left # 找后继节点 successor root.right while successor.left: successor successor.left root.val successor.val root.right deleteNode(root.right, successor.val) return root6. 将有序数组转换为二叉搜索树6.1 平衡BST构建原理有序数组的中点是平衡BST的根节点递归构建左右子树def sortedArrayToBST(nums): def helper(left, right): if left right: return None mid (left right) // 2 root TreeNode(nums[mid]) root.left helper(left, mid - 1) root.right helper(mid 1, right) return root return helper(0, len(nums) - 1)6.2 迭代实现使用栈模拟递归过程def sortedArrayToBSTIterative(nums): if not nums: return None root TreeNode(0) stack [(0, len(nums) - 1, root)] while stack: left, right, node stack.pop() mid (left right) // 2 node.val nums[mid] if left mid - 1: node.left TreeNode(0) stack.append((left, mid - 1, node.left)) if mid 1 right: node.right TreeNode(0) stack.append((mid 1, right, node.right)) return root7. 二叉树算法实战技巧7.1 递归转迭代的通用方法当处理深度较大的树时递归可能导致栈溢出。通用转换方法使用显式栈替代调用栈将递归参数存入栈中使用循环处理栈元素用标记位区分已处理和未处理节点7.2 边界条件处理经验空树检查应放在递归开始而非中间对于BST操作注意维护树的性质删除节点时要正确处理内存(如C等语言)7.3 调试与验证技巧编写树遍历打印函数验证结构对BST进行中序遍历验证有序性使用小规模测试用例(3-5个节点)快速验证def inorderTraversal(root): res [] stack [] curr root while curr or stack: while curr: stack.append(curr) curr curr.left curr stack.pop() res.append(curr.val) curr curr.right return res8. 复杂度分析与优化方向算法时间复杂度空间复杂度优化思路合并二叉树O(n)O(h)迭代法减少栈空间BST搜索O(h)O(1)迭代法避免递归LCAO(n)O(h)路径记录法可优化空间BST删除O(h)O(h)尾递归优化数组转BSTO(n)O(logn)迭代法减少栈空间对于大规模数据可以考虑使用Morris遍历实现O(1)空间算法对BST进行平衡操作(AVL/红黑树)对频繁操作实现批处理版本