前端算法冲刺指南：树结构与8道高频题精解

2025年12月16日 互联网

前端算法冲刺指南：树结构与8道高频题精解

在前端技术面试中，算法题始终是绕不开的核心环节。其中，树结构相关题目因其能考察递归思维、数据结构操作能力而备受青睐。本文精选8道高频树算法题，从基础遍历到复杂应用，结合代码实现与优化思路，助力开发者系统提升解题能力。

一、树结构的核心考点

树作为非线性数据结构，其核心操作围绕节点关系展开。前端面试中，二叉树是主要考察对象，重点包括：

  1. 遍历方式：前序/中序/后序遍历的递归与迭代实现
  2. 节点关系：父子节点查找、最近公共祖先（LCA）
  3. 结构特性：平衡性校验、对称性判断
  4. 应用场景：序列化/反序列化、路径和计算

二、8道高频题详解

1. 二叉树的前序遍历（LeetCode 144）

题目：给定二叉树根节点，返回前序遍历结果（根-左-右）。
解法：

  1. // 递归解法
  2. function preorderTraversal(root) {
  3.   const res = [];
  4.   function traverse(node) {
  5.     if (!node) return;
  6.     res.push(node.val);  // 访问根节点
  7.     traverse(node.left); // 遍历左子树
  8.     traverse(node.right);// 遍历右子树
  9.   }
  10.   traverse(root);
  11.   return res;
  12. }
  14. // 迭代解法（显式栈）
  15. function preorderTraversal(root) {
  16.   const res = [], stack = [];
  17.   if (root) stack.push(root);
  18.   while (stack.length) {
  19.     const node = stack.pop();
  20.     res.push(node.val);
  21.     // 注意右子树先入栈，保证左子树先处理
  22.     if (node.right) stack.push(node.right);
  23.     if (node.left) stack.push(node.left);
  24.   }
  25.   return res;
  26. }

关键点：递归终止条件、栈的入栈顺序。时间复杂度O(n)，空间复杂度O(h)（h为树高）。

2. 二叉树的最近公共祖先（LCA，LeetCode 236）

题目：给定二叉树和两个节点p、q，返回它们的最近公共祖先。
解法：

  1. function lowestCommonAncestor(root, p, q) {
  2.   if (!root || root === p || root === q) return root;
  3.   const left = lowestCommonAncestor(root.left, p, q);
  4.   const right = lowestCommonAncestor(root.right, p, q);
  5.   // 分三种情况：
  6.   // 1. p和q分别在左右子树中
  7.   // 2. p和q都在左子树中
  8.   // 3. p和q都在右子树中
  9.   return left && right ? root : (left || right);
  10. }

优化思路：后序遍历自底向上搜索，避免重复计算。时间复杂度O(n)。

3. 平衡二叉树校验（LeetCode 110）

题目：判断二叉树是否是高度平衡的（左右子树高度差不超过1）。
解法：

  1. function isBalanced(root) {
  2.   function checkHeight(node) {
  3.     if (!node) return 0;
  4.     const leftHeight = checkHeight(node.left);
  5.     const rightHeight = checkHeight(node.right);
  6.     // 提前终止：发现不平衡立即返回
  7.     if (leftHeight === -1 || rightHeight === -1 || 
  8.         Math.abs(leftHeight - rightHeight) > 1) {
  9.       return -1;
  10.     }
  11.     return Math.max(leftHeight, rightHeight) + 1;
  12.   }
  13.   return checkHeight(root) !== -1;
  14. }

关键点：自底向上计算高度，发现不平衡立即终止递归。

4. 对称二叉树判断（LeetCode 101）

题目：判断二叉树是否对称（镜像反射后相同）。
解法：

  1. function isSymmetric(root) {
  2.   function isMirror(left, right) {
  3.     if (!left && !right) return true;
  4.     if (!left || !right) return false;
  5.     return (left.val === right.val) && 
  6.            isMirror(left.left, right.right) && 
  7.            isMirror(left.right, right.left);
  8.   }
  9.   return isMirror(root?.left, root?.right);
  10. }

递归逻辑：比较左子树的左节点与右子树的右节点，左子树的右节点与右子树的左节点。

5. 二叉树路径和（LeetCode 112）

题目：判断是否存在从根节点到叶子节点的路径，使得路径和等于目标值。
解法：

  1. function hasPathSum(root, targetSum) {
  2.   if (!root) return false;
  3.   // 叶子节点判断
  4.   if (!root.left && !root.right) {
  5.     return targetSum === root.val;
  6.   }
  7.   return hasPathSum(root.left, targetSum - root.val) || 
  8.          hasPathSum(root.right, targetSum - root.val);
  9. }

注意事项：递归时需减去当前节点值，叶子节点需同时满足无子节点和值匹配。

6. 二叉搜索树验证（LeetCode 98）

题目：判断二叉树是否是二叉搜索树（BST）。
解法（中序遍历法）：

  1. function isValidBST(root) {
  2.   let prev = null;
  3.   function inorder(node) {
  4.     if (!node) return true;
  5.     if (!inorder(node.left)) return false;
  6.     if (prev !== null && node.val <= prev) return false;
  7.     prev = node.val;
  8.     return inorder(node.right);
  9.   }
  10.   return inorder(root);
  11. }

原理：BST的中序遍历结果应为严格递增序列。

7. 二叉树的层序遍历（LeetCode 102）

题目：按层返回二叉树的节点值。
解法（BFS）：

  1. function levelOrder(root) {
  2.   const res = [];
  3.   if (!root) return res;
  4.   const queue = [root];
  5.   while (queue.length) {
  6.     const levelSize = queue.length;
  7.     const currentLevel = [];
  8.     for (let i = 0; i < levelSize; i++) {
  9.       const node = queue.shift();
  10.       currentLevel.push(node.val);
  11.       if (node.left) queue.push(node.left);
  12.       if (node.right) queue.push(node.right);
  13.     }
  14.     res.push(currentLevel);
  15.   }
  16.   return res;
  17. }

关键点：记录每层节点数，控制内层循环次数。

8. 二叉树的序列化与反序列化（LeetCode 297）

题目：设计算法将二叉树序列化为字符串，并能从字符串还原二叉树。
解法（前序遍历+标记空节点）：

  1. // 序列化
  2. function serialize(root) {
  3.   const res = [];
  4.   function dfs(node) {
  5.     if (!node) {
  6.       res.push('null');
  7.       return;
  8.     }
  9.     res.push(node.val.toString());
  10.     dfs(node.left);
  11.     dfs(node.right);
  12.   }
  13.   dfs(root);
  14.   return res.join(',');
  15. }
  17. // 反序列化
  18. function deserialize(data) {
  19.   const arr = data.split(',');
  20.   let index = 0;
  21.   function dfs() {
  22.     if (arr[index] === 'null') {
  23.       index++;
  24.       return null;
  25.     }
  26.     const node = { val: parseInt(arr[index]), left: null, right: null };
  27.     index++;
  28.     node.left = dfs();
  29.     node.right = dfs();
  30.     return node;
  31.   }
  32.   return dfs();
  33. }

注意事项：需标记空节点，否则无法区分缺失的左右子树。

三、备考建议

  1. 递归思维训练：树问题80%可通过递归解决，重点理解递归终止条件和子问题分解。
  2. 迭代法补充：对于深度较大的树，迭代法（显式栈/队列）可避免栈溢出。
  3. 边界条件处理：空树、单节点树、完全不平衡树等特殊情况需单独测试。
  4. 复杂度分析：面试中需说明时间复杂度（通常O(n)）和空间复杂度（O(h)）。

通过系统练习这8道典型题，可覆盖树结构90%以上的面试考点。建议结合LeetCode等平台进行限时训练，逐步提升解题速度与代码质量。

最新文章