1. 二叉树基础概念与常见问题分类二叉树是数据结构中最基础也最重要的非线性结构之一它由节点和边组成每个节点最多有两个子节点。在实际编程面试和算法应用中二叉树相关问题出现的频率极高。根据我的经验面试中遇到的二叉树问题大致可以分为以下几类深度/高度相关如计算最小深度、最大深度节点统计如计算节点总数、叶子节点数平衡性判断如判断是否为平衡二叉树路径问题如路径总和、最长路径构建问题如根据遍历序列重建二叉树今天我们就来深入探讨标题中提到的五个典型问题最小深度、完全二叉树的节点个数、平衡二叉树判断、路径总和以及根据遍历序列构建二叉树。这些都是力扣(LeetCode)上的高频题目也是面试中的常客。2. 二叉树的最小深度计算2.1 最小深度的定义与常见误区二叉树的最小深度是指从根节点到最近叶子节点的最短路径上的节点数量。这里有个常见的误区很多人会把最小深度简单理解为左子树和右子树深度的较小值这种理解是错误的。考虑下面这个简单的二叉树1 / 2按照错误理解左子树深度为1右子树深度为0取较小值011。但实际上最小深度应该是2因为节点1不是叶子节点最近的叶子节点是节点2。2.2 递归解法与实现正确的递归解法需要考虑以下几种情况当前节点为空返回0当前节点的左右子节点都为空返回1当前节点的左右子节点有一个为空返回非空子树的最小深度1当前节点的左右子节点都不为空返回左右子树最小深度的较小值1Python实现代码如下def minDepth(root): if not root: return 0 if not root.left and not root.right: return 1 if not root.left: return minDepth(root.right) 1 if not root.right: return minDepth(root.left) 1 return min(minDepth(root.left), minDepth(root.right)) 12.3 迭代解法与性能对比递归解法虽然直观但在极端情况下如树极度不平衡可能导致栈溢出。我们可以使用广度优先搜索(BFS)的迭代解法它能在找到第一个叶子节点时立即返回结果效率更高。from collections import deque def minDepth(root): if not root: return 0 queue deque([(root, 1)]) while queue: node, depth queue.popleft() if not node.left and not node.right: return depth if node.left: queue.append((node.left, depth 1)) if node.right: queue.append((node.right, depth 1)) return 0在实际应用中如果树比较平衡递归解法的代码更简洁如果树可能极度不平衡迭代解法更可靠。3. 完全二叉树的节点个数计算3.1 完全二叉树的定义与特性完全二叉树是指除了最后一层外其他层的节点都达到最大数量且最后一层的节点都集中在左侧。这种结构有以下重要特性对于高度为h的完全二叉树前h-1层是满二叉树节点数为2^(h-1)-1最后一层的节点数在1到2^(h-1)之间左子树的高度总是大于或等于右子树的高度3.2 普通二叉树的节点计数方法对于任意二叉树计算节点数的常规方法是递归遍历def countNodes(root): if not root: return 0 return 1 countNodes(root.left) countNodes(root.right)这种方法的时间复杂度是O(n)对于完全二叉树来说没有利用其特性效率不高。3.3 利用完全二叉树特性的高效算法我们可以利用完全二叉树的特性设计更高效的算法计算左子树的高度left_height计算右子树的高度right_height如果left_height right_height说明左子树是满二叉树如果left_height ! right_height说明右子树是满二叉树def countNodes(root): if not root: return 0 left_height get_height(root.left) right_height get_height(root.right) if left_height right_height: return (1 left_height) countNodes(root.right) else: return (1 right_height) countNodes(root.left) def get_height(node): height 0 while node: height 1 node node.left return height这个算法的时间复杂度是O(log n * log n)因为每次递归调用都减少了一半的问题规模而每次计算高度需要O(log n)时间。4. 平衡二叉树的判断4.1 平衡二叉树的定义平衡二叉树是指任意节点的左右子树高度差不超过1的二叉树。这个定义是递归的意味着所有子树也必须满足这个条件。4.2 自顶向下的递归方法最直观的方法是对于每个节点计算其左右子树的高度差def isBalanced(root): if not root: return True left_height height(root.left) right_height height(root.right) return abs(left_height - right_height) 1 and \ isBalanced(root.left) and \ isBalanced(root.right) def height(node): if not node: return 0 return max(height(node.left), height(node.right)) 1这种方法的时间复杂度是O(n^2)因为对于每个节点都要计算其子树的高度存在大量重复计算。4.3 自底向上的优化方法我们可以通过后序遍历优化在计算高度的同时判断平衡性def isBalanced(root): return check_height(root) ! -1 def check_height(node): if not node: return 0 left_height check_height(node.left) if left_height -1: return -1 right_height check_height(node.right) if right_height -1: return -1 if abs(left_height - right_height) 1: return -1 return max(left_height, right_height) 1这种方法的时间复杂度是O(n)因为每个节点只被访问一次。当发现任何子树不平衡时会立即返回-1提前终止递归。5. 路径总和问题5.1 问题描述与基本解法路径总和问题要求判断二叉树中是否存在从根节点到叶子节点的路径使得路径上所有节点的值之和等于给定的目标值。递归解法思路如果当前节点为空返回False如果当前节点是叶子节点检查剩余和是否等于节点值否则递归检查左右子树目标值减去当前节点值def hasPathSum(root, targetSum): if not root: return False if not root.left and not root.right: return targetSum root.val return hasPathSum(root.left, targetSum - root.val) or \ hasPathSum(root.right, targetSum - root.val)5.2 扩展问题记录所有满足条件的路径有时我们需要找出所有满足条件的路径而不仅仅是判断是否存在。这时需要记录路径def pathSum(root, targetSum): result [] dfs(root, targetSum, [], result) return result def dfs(node, remaining, path, result): if not node: return path.append(node.val) if not node.left and not node.right and remaining node.val: result.append(list(path)) dfs(node.left, remaining - node.val, path, result) dfs(node.right, remaining - node.val, path, result) path.pop()注意这里使用了回溯法在递归返回前要弹出当前节点值确保路径的正确性。5.3 迭代解法与性能考虑递归解法简洁但可能有栈溢出风险。迭代解法使用栈模拟递归def hasPathSum(root, targetSum): if not root: return False stack [(root, targetSum - root.val)] while stack: node, remaining stack.pop() if not node.left and not node.right and remaining 0: return True if node.right: stack.append((node.right, remaining - node.right.val)) if node.left: stack.append((node.left, remaining - node.left.val)) return False迭代解法在空间复杂度上通常优于递归解法特别是对于不平衡的树。6. 从中序与后序遍历序列构造二叉树6.1 遍历序列的特性分析中序遍历的顺序是左子树 - 根节点 - 右子树 后序遍历的顺序是左子树 - 右子树 - 根节点关键观察后序遍历的最后一个元素是根节点在中序遍历中找到这个根节点左边是左子树右边是右子树根据左子树的长度可以在后序遍历中划分出左右子树的后序遍历序列6.2 递归构建算法def buildTree(inorder, postorder): if not inorder or not postorder: return None root_val postorder[-1] root TreeNode(root_val) root_index inorder.index(root_val) root.left buildTree(inorder[:root_index], postorder[:root_index]) root.right buildTree(inorder[root_index1:], postorder[root_index:-1]) return root这个算法的时间复杂度是O(n^2)因为每次都要在中序遍历中查找根节点的位置。可以通过哈希表优化查找过程。6.3 优化使用哈希表加速查找def buildTree(inorder, postorder): inorder_map {val: idx for idx, val in enumerate(inorder)} def helper(in_start, in_end, post_start, post_end): if in_start in_end: return None root_val postorder[post_end] root TreeNode(root_val) root_index inorder_map[root_val] left_size root_index - in_start root.left helper(in_start, root_index - 1, post_start, post_start left_size - 1) root.right helper(root_index 1, in_end, post_start left_size, post_end - 1) return root return helper(0, len(inorder) - 1, 0, len(postorder) - 1)优化后的算法时间复杂度降为O(n)因为每次查找根节点位置的时间是O(1)。6.4 边界条件与注意事项在实际实现中需要注意输入序列为空的情况输入序列长度不一致的情况序列中包含重复值的情况这种情况下无法唯一确定二叉树递归终止条件的正确设置我在实际项目中遇到过因为忽略空序列检查而导致递归深度过大的问题特别是在处理边缘用例时。建议在实现前先考虑清楚所有可能的边界情况。 二叉树算法精解：最小深度、节点计数与平衡判断
1. 二叉树基础概念与常见问题分类二叉树是数据结构中最基础也最重要的非线性结构之一它由节点和边组成每个节点最多有两个子节点。在实际编程面试和算法应用中二叉树相关问题出现的频率极高。根据我的经验面试中遇到的二叉树问题大致可以分为以下几类深度/高度相关如计算最小深度、最大深度节点统计如计算节点总数、叶子节点数平衡性判断如判断是否为平衡二叉树路径问题如路径总和、最长路径构建问题如根据遍历序列重建二叉树今天我们就来深入探讨标题中提到的五个典型问题最小深度、完全二叉树的节点个数、平衡二叉树判断、路径总和以及根据遍历序列构建二叉树。这些都是力扣(LeetCode)上的高频题目也是面试中的常客。2. 二叉树的最小深度计算2.1 最小深度的定义与常见误区二叉树的最小深度是指从根节点到最近叶子节点的最短路径上的节点数量。这里有个常见的误区很多人会把最小深度简单理解为左子树和右子树深度的较小值这种理解是错误的。考虑下面这个简单的二叉树1 / 2按照错误理解左子树深度为1右子树深度为0取较小值011。但实际上最小深度应该是2因为节点1不是叶子节点最近的叶子节点是节点2。2.2 递归解法与实现正确的递归解法需要考虑以下几种情况当前节点为空返回0当前节点的左右子节点都为空返回1当前节点的左右子节点有一个为空返回非空子树的最小深度1当前节点的左右子节点都不为空返回左右子树最小深度的较小值1Python实现代码如下def minDepth(root): if not root: return 0 if not root.left and not root.right: return 1 if not root.left: return minDepth(root.right) 1 if not root.right: return minDepth(root.left) 1 return min(minDepth(root.left), minDepth(root.right)) 12.3 迭代解法与性能对比递归解法虽然直观但在极端情况下如树极度不平衡可能导致栈溢出。我们可以使用广度优先搜索(BFS)的迭代解法它能在找到第一个叶子节点时立即返回结果效率更高。from collections import deque def minDepth(root): if not root: return 0 queue deque([(root, 1)]) while queue: node, depth queue.popleft() if not node.left and not node.right: return depth if node.left: queue.append((node.left, depth 1)) if node.right: queue.append((node.right, depth 1)) return 0在实际应用中如果树比较平衡递归解法的代码更简洁如果树可能极度不平衡迭代解法更可靠。3. 完全二叉树的节点个数计算3.1 完全二叉树的定义与特性完全二叉树是指除了最后一层外其他层的节点都达到最大数量且最后一层的节点都集中在左侧。这种结构有以下重要特性对于高度为h的完全二叉树前h-1层是满二叉树节点数为2^(h-1)-1最后一层的节点数在1到2^(h-1)之间左子树的高度总是大于或等于右子树的高度3.2 普通二叉树的节点计数方法对于任意二叉树计算节点数的常规方法是递归遍历def countNodes(root): if not root: return 0 return 1 countNodes(root.left) countNodes(root.right)这种方法的时间复杂度是O(n)对于完全二叉树来说没有利用其特性效率不高。3.3 利用完全二叉树特性的高效算法我们可以利用完全二叉树的特性设计更高效的算法计算左子树的高度left_height计算右子树的高度right_height如果left_height right_height说明左子树是满二叉树如果left_height ! right_height说明右子树是满二叉树def countNodes(root): if not root: return 0 left_height get_height(root.left) right_height get_height(root.right) if left_height right_height: return (1 left_height) countNodes(root.right) else: return (1 right_height) countNodes(root.left) def get_height(node): height 0 while node: height 1 node node.left return height这个算法的时间复杂度是O(log n * log n)因为每次递归调用都减少了一半的问题规模而每次计算高度需要O(log n)时间。4. 平衡二叉树的判断4.1 平衡二叉树的定义平衡二叉树是指任意节点的左右子树高度差不超过1的二叉树。这个定义是递归的意味着所有子树也必须满足这个条件。4.2 自顶向下的递归方法最直观的方法是对于每个节点计算其左右子树的高度差def isBalanced(root): if not root: return True left_height height(root.left) right_height height(root.right) return abs(left_height - right_height) 1 and \ isBalanced(root.left) and \ isBalanced(root.right) def height(node): if not node: return 0 return max(height(node.left), height(node.right)) 1这种方法的时间复杂度是O(n^2)因为对于每个节点都要计算其子树的高度存在大量重复计算。4.3 自底向上的优化方法我们可以通过后序遍历优化在计算高度的同时判断平衡性def isBalanced(root): return check_height(root) ! -1 def check_height(node): if not node: return 0 left_height check_height(node.left) if left_height -1: return -1 right_height check_height(node.right) if right_height -1: return -1 if abs(left_height - right_height) 1: return -1 return max(left_height, right_height) 1这种方法的时间复杂度是O(n)因为每个节点只被访问一次。当发现任何子树不平衡时会立即返回-1提前终止递归。5. 路径总和问题5.1 问题描述与基本解法路径总和问题要求判断二叉树中是否存在从根节点到叶子节点的路径使得路径上所有节点的值之和等于给定的目标值。递归解法思路如果当前节点为空返回False如果当前节点是叶子节点检查剩余和是否等于节点值否则递归检查左右子树目标值减去当前节点值def hasPathSum(root, targetSum): if not root: return False if not root.left and not root.right: return targetSum root.val return hasPathSum(root.left, targetSum - root.val) or \ hasPathSum(root.right, targetSum - root.val)5.2 扩展问题记录所有满足条件的路径有时我们需要找出所有满足条件的路径而不仅仅是判断是否存在。这时需要记录路径def pathSum(root, targetSum): result [] dfs(root, targetSum, [], result) return result def dfs(node, remaining, path, result): if not node: return path.append(node.val) if not node.left and not node.right and remaining node.val: result.append(list(path)) dfs(node.left, remaining - node.val, path, result) dfs(node.right, remaining - node.val, path, result) path.pop()注意这里使用了回溯法在递归返回前要弹出当前节点值确保路径的正确性。5.3 迭代解法与性能考虑递归解法简洁但可能有栈溢出风险。迭代解法使用栈模拟递归def hasPathSum(root, targetSum): if not root: return False stack [(root, targetSum - root.val)] while stack: node, remaining stack.pop() if not node.left and not node.right and remaining 0: return True if node.right: stack.append((node.right, remaining - node.right.val)) if node.left: stack.append((node.left, remaining - node.left.val)) return False迭代解法在空间复杂度上通常优于递归解法特别是对于不平衡的树。6. 从中序与后序遍历序列构造二叉树6.1 遍历序列的特性分析中序遍历的顺序是左子树 - 根节点 - 右子树 后序遍历的顺序是左子树 - 右子树 - 根节点关键观察后序遍历的最后一个元素是根节点在中序遍历中找到这个根节点左边是左子树右边是右子树根据左子树的长度可以在后序遍历中划分出左右子树的后序遍历序列6.2 递归构建算法def buildTree(inorder, postorder): if not inorder or not postorder: return None root_val postorder[-1] root TreeNode(root_val) root_index inorder.index(root_val) root.left buildTree(inorder[:root_index], postorder[:root_index]) root.right buildTree(inorder[root_index1:], postorder[root_index:-1]) return root这个算法的时间复杂度是O(n^2)因为每次都要在中序遍历中查找根节点的位置。可以通过哈希表优化查找过程。6.3 优化使用哈希表加速查找def buildTree(inorder, postorder): inorder_map {val: idx for idx, val in enumerate(inorder)} def helper(in_start, in_end, post_start, post_end): if in_start in_end: return None root_val postorder[post_end] root TreeNode(root_val) root_index inorder_map[root_val] left_size root_index - in_start root.left helper(in_start, root_index - 1, post_start, post_start left_size - 1) root.right helper(root_index 1, in_end, post_start left_size, post_end - 1) return root return helper(0, len(inorder) - 1, 0, len(postorder) - 1)优化后的算法时间复杂度降为O(n)因为每次查找根节点位置的时间是O(1)。6.4 边界条件与注意事项在实际实现中需要注意输入序列为空的情况输入序列长度不一致的情况序列中包含重复值的情况这种情况下无法唯一确定二叉树递归终止条件的正确设置我在实际项目中遇到过因为忽略空序列检查而导致递归深度过大的问题特别是在处理边缘用例时。建议在实现前先考虑清楚所有可能的边界情况。