前端树结构算法与高频面试题精解

一、树结构基础与前端场景

树（Tree）是一种非线性数据结构，由根节点、子节点和边组成，具有层级关系。在前端开发中，树结构的应用极为广泛，例如DOM树（页面元素层级）、虚拟DOM的差异计算、组件树的递归渲染、路由配置的嵌套规则，以及状态管理中的嵌套数据结构。

树的核心特性包括：

层级性：每个节点（除根节点）有且仅有一个父节点；
递归性：子树本身也是一棵树，适合用递归处理；
多样性：二叉树、多叉树、平衡树等变种适用于不同场景。

例如，React/Vue的组件树通过递归渲染实现嵌套组件的展示，而路由配置中的嵌套路由本质上是树结构的路径匹配。理解树结构的基础操作（遍历、搜索、修改）是解决前端复杂问题的关键。

二、8道高频树算法面试题解析

1. 树的深度优先遍历（DFS）与广度优先遍历（BFS）

问题：如何实现树的深度优先和广度优先遍历？
解析：

DFS：递归或栈实现，优先访问子节点。适用于需要深度搜索的场景（如查找特定节点）。
BFS：队列实现，按层级访问节点。适用于最短路径或层级相关问题（如计算树的最大宽度）。

代码示例（DFS递归）：

function dfs(node, callback) {
  if (!node) return;
  callback(node.value); // 前序遍历
  dfs(node.left, callback);
  dfs(node.right, callback);
  // callback(node.value); // 后序遍历（调整位置）
}

优化点：递归可能导致栈溢出，可改用显式栈实现迭代DFS。

2. 二叉树的最大深度

问题：给定二叉树，求其最大深度（根节点到最远叶子节点的路径长度）。
解析：递归计算左右子树的最大深度，取较大值加1。时间复杂度O(n)，空间复杂度O(h)（h为树高）。

代码示例：

function maxDepth(root) {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

3. 对称二叉树判断

问题：判断一棵二叉树是否对称（镜像对称）。
解析：递归比较左子树的左节点与右子树的右节点，左子树的右节点与右子树的左节点。

代码示例：

function isSymmetric(root) {
  if (!root) return true;
  const isMirror = (left, right) => {
    if (!left && !right) return true;
    if (!left || !right) return false;
    return left.val === right.val && 
           isMirror(left.left, right.right) && 
           isMirror(left.right, right.left);
  };
  return isMirror(root.left, root.right);
}

4. 路径总和

问题：给定二叉树和一个目标和，判断是否存在从根节点到叶子节点的路径，其节点值之和等于目标和。
解析：递归计算路径和，若到达叶子节点且和等于目标则返回true。

代码示例：

function hasPathSum(root, targetSum) {
  if (!root) return false;
  if (!root.left && !root.right) return targetSum === root.val;
  return hasPathSum(root.left, targetSum - root.val) || 
         hasPathSum(root.right, targetSum - root.val);
}

5. 二叉树的层序遍历

问题：按层级打印二叉树的节点值。
解析：使用队列实现BFS，记录每层的节点数。

代码示例：

function levelOrder(root) {
  if (!root) return [];
  const queue = [root], result = [];
  while (queue.length) {
    const levelSize = queue.length;
    const currentLevel = [];
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      currentLevel.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(currentLevel);
  }
  return result;
}

6. 最近公共祖先（LCA）

问题：给定二叉树和两个节点p、q，求它们的最近公共祖先。
解析：递归查找p和q，若当前节点为p或q，或左右子树分别包含p和q，则当前节点为LCA。

代码示例：

function lowestCommonAncestor(root, p, q) {
  if (!root || root === p || root === q) return root;
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);
  if (left && right) return root;
  return left || right;
}

7. 序列化与反序列化二叉树

问题：将二叉树序列化为字符串，并能从字符串还原二叉树。
解析：前序遍历序列化，用特殊字符（如”#”）表示空节点；反序列化时递归构建树。

代码示例：

// 序列化
function serialize(root) {
  if (!root) return "#";
  return `${root.val},${serialize(root.left)},${serialize(root.right)}`;
}
// 反序列化
function deserialize(data) {
  const nodes = data.split(",");
  let index = 0;
  const buildTree = () => {
    const val = nodes[index++];
    if (val === "#") return null;
    const node = { val: parseInt(val), left: null, right: null };
    node.left = buildTree();
    node.right = buildTree();
    return node;
  };
  return buildTree();
}

8. 平衡二叉树判断

问题：判断二叉树是否为平衡二叉树（任意节点的左右子树高度差不超过1）。
解析：自底向上递归，计算子树高度并判断平衡性。

代码示例：

function isBalanced(root) {
  const checkHeight = (node) => {
    if (!node) return 0;
    const leftHeight = checkHeight(node.left);
    const rightHeight = checkHeight(node.right);
    if (leftHeight === -1 || rightHeight === -1 || 
        Math.abs(leftHeight - rightHeight) > 1) {
      return -1;
    }
    return 1 + Math.max(leftHeight, rightHeight);
  };
  return checkHeight(root) !== -1;
}

三、性能优化与最佳实践

递归转迭代：对于深度较大的树，递归可能导致栈溢出，可用显式栈或队列替代。
剪枝优化：在搜索类问题中，提前终止无效分支（如路径和中已超过目标和时直接返回）。
缓存子问题结果：对于重复计算的子树（如平衡树的高度），可缓存结果避免重复计算。
空间复杂度分析：BFS的空间复杂度为O(w)（w为最大宽度），DFS为O(h)（h为高度），根据场景选择。

四、总结与刷题建议

树结构算法是前端面试的高频考点，掌握其核心思想（递归、分治、层级处理）和常见变种（二叉树、多叉树）至关重要。建议通过以下方式提升能力：

分题型练习：按遍历、搜索、修改等类别分类刷题；
代码模板化：总结DFS/BFS的代码模板，快速适配不同问题；
复杂度分析：每道题分析时间与空间复杂度，培养优化思维。

通过系统练习，开发者不仅能高效通过面试，还能在实际项目中灵活应用树结构解决复杂问题。