Knowledge_Repository

主题

Teeker2026-04-06
1793
7.4m

二叉树核心题及完整解答（2023 年 10 月 01 日） ​

你希望我把前端机试中二叉树的核心高频题目和对应的完整解答汇总出来，方便你集中复习、直接套用，我会按「题目+核心思路+完整JS代码（带注释）+ 测试示例」的形式整理，所有代码都是前端机试中可直接手写的最优版本。

二叉树核心题及完整解答（前端机试高频版） ​

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

题目：给定二叉树根节点，返回节点值的前序遍历（根→左→右）。

核心思路：递归遍历，先处理当前节点，再递归左、右子树（最易写，机试优先用）。

JavaScript

// 前序遍历（递归版，机试首选）
function preorderTraversal(root) {
    const result = []; // 存储遍历结果
    // 定义递归辅助函数
    const traverse = (node) => {
        if (!node) return; // 终止条件：节点为空
        result.push(node.val); // 1. 先存根节点值（核心）
        traverse(node.left);   // 2. 递归遍历左子树
        traverse(node.right);  // 3. 递归遍历右子树
    };
    traverse(root);
    return result;
}

// 测试示例：
// 树结构：    1
//           /   \
//          2     3
const root = new TreeNode(1, new TreeNode(2), new TreeNode(3));
console.log(preorderTraversal(root)); // 输出：[1,2,3]

2. 二叉树的中序遍历（LeetCode 94） ​

题目：返回二叉树节点值的中序遍历（左→根→右）（二叉搜索树必用）。

核心思路：递归先遍历左子树，再处理当前节点，最后遍历右子树。

JavaScript

function inorderTraversal(root) {
    const result = [];
    const traverse = (node) => {
        if (!node) return;
        traverse(node.left);   // 1. 先递归左子树（核心）
        result.push(node.val); // 2. 存根节点值
        traverse(node.right);  // 3. 递归右子树
    };
    traverse(root);
    return result;
}

// 测试：用上面的树，输出 [2,1,3]
console.log(inorderTraversal(root)); // [2,1,3]

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

题目：按层输出二叉树节点值（如[[1],[2,3]]），也叫广度优先遍历。

核心思路：用队列存储当前层节点，遍历完一层再处理下一层。

JavaScript

function levelOrder(root) {
    const result = [];
    if (!root) return result; // 空树直接返回空数组
    const queue = [root]; // 队列初始化，存入根节点
    
    while (queue.length > 0) {
        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;
}

// 测试：用上面的树，输出 [[1],[2,3]]
console.log(levelOrder(root)); // [[1],[2,3]]

4. 二叉树的最大深度（LeetCode 104） ​

题目：求二叉树的最大深度（根节点到最远叶子节点的层数）。

核心思路：后序遍历思想，递归求左右子树深度，取最大值+1（当前层）。

JavaScript

function maxDepth(root) {
    // 终止条件：空节点深度为0
    if (!root) return 0;
    // 递归求左子树深度
    const leftDepth = maxDepth(root.left);
    // 递归求右子树深度
    const rightDepth = maxDepth(root.right);
    // 当前节点深度 = 左右子树最大深度 + 1
    return Math.max(leftDepth, rightDepth) + 1;
}

// 测试：用上面的树，输出 2
console.log(maxDepth(root)); // 2

5. 翻转二叉树（LeetCode 226） ​

题目：翻转二叉树（所有节点的左右子节点互换），前端机试必考。

核心思路：递归交换每个节点的左右子节点，从根到叶子依次翻转。

JavaScript

function invertTree(root) {
    // 终止条件：空节点直接返回
    if (!root) return null;
    // 交换当前节点的左右子节点（核心）
    [root.left, root.right] = [root.right, root.left];
    // 递归翻转左子树
    invertTree(root.left);
    // 递归翻转右子树
    invertTree(root.right);
    // 返回翻转后的根节点
    return root;
}

// 测试：翻转后树结构为 1 / \ 3 2，前序遍历输出 [1,3,2]
const invertedRoot = invertTree(root);
console.log(preorderTraversal(invertedRoot)); // [1,3,2]

6. 对称二叉树（LeetCode 101） ​

题目：判断一棵二叉树是否轴对称（左右子树镜像相等）。

核心思路：递归比较「左子树的左节点 vs 右子树的右节点」「左子树的右节点 vs 右子树的左节点」。

JavaScript

function isSymmetric(root) {
    // 辅助函数：比较两个节点是否镜像
    const isMirror = (leftNode, rightNode) => {
        // 两个节点都为空 → 镜像
        if (!leftNode && !rightNode) return true;
        // 一个空一个非空 → 不镜像
        if (!leftNode || !rightNode) return false;
        // 节点值相等 + 左左=右右 + 左右=右左 → 镜像
        return leftNode.val === rightNode.val 
            && isMirror(leftNode.left, rightNode.right) 
            && isMirror(leftNode.right, rightNode.left);
    };
    // 从根节点的左右子树开始比较
    return isMirror(root, root);
}

// 测试1：对称树（输入如下），输出 true
//      1
//     / \
//    2   2
//   / \ / \
//  3  4 4  3
const symmetricRoot = new TreeNode(1,
    new TreeNode(2, new TreeNode(3), new TreeNode(4)),
    new TreeNode(2, new TreeNode(4), new TreeNode(3))
);
console.log(isSymmetric(symmetricRoot)); // true

// 测试2：原树（1/2 3），输出 false
console.log(isSymmetric(root)); // false

7. 路径总和（LeetCode 112） ​

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

核心思路：前序遍历+回溯，递归时减去当前节点值，叶子节点判断是否等于剩余值。

JavaScript

function hasPathSum(root, targetSum) {
    // 空树直接返回false
    if (!root) return false;
    // 叶子节点：判断当前值是否等于剩余目标值（核心）
    if (!root.left && !root.right) return root.val === targetSum;
    // 递归左子树：目标值减去当前节点值
    const leftHas = hasPathSum(root.left, targetSum - root.val);
    // 递归右子树：目标值减去当前节点值
    const rightHas = hasPathSum(root.right, targetSum - root.val);
    // 只要左/右子树有一个满足就返回true
    return leftHas || rightHas;
}

// 测试：树 1/2 3，目标值3 → 路径1→2，和为3，输出true
console.log(hasPathSum(root, 3)); // true
// 目标值5 → 无路径，输出false
console.log(hasPathSum(root, 5)); // false

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

题目：判断一棵二叉树是否是有效的二叉搜索树（BST）。

核心思路：BST的中序遍历结果是严格递增的，遍历过程中判断是否满足递增。

JavaScript

function isValidBST(root) {
    let prevVal = -Infinity; // 记录上一个节点的值，初始为负无穷
    let isValid = true;      // 标记是否有效
    
    // 中序遍历辅助函数
    const traverse = (node) => {
        if (!node || !isValid) return; // 空节点/已确定无效，直接返回
        traverse(node.left); // 遍历左子树
        
        // 核心判断：当前节点值 ≤ 上一个节点值 → 不是BST
        if (node.val <= prevVal) {
            isValid = false;
            return;
        }
        prevVal = node.val; // 更新上一个节点值
        
        traverse(node.right); // 遍历右子树
    };
    
    traverse(root);
    return isValid;
}

// 测试1：有效BST（2/1 3），输出true
const bstRoot = new TreeNode(2, new TreeNode(1), new TreeNode(3));
console.log(isValidBST(bstRoot)); // true

// 测试2：无效BST（1/2 3），输出false
console.log(isValidBST(root)); // false

总结 ​

  1. 核心模板：递归遍历（前/中/层序）是所有题的基础，必须背熟；翻转、最大深度等题都是遍历的简单变形。

  2. 必拿分题：翻转二叉树、最大深度、前序/层序遍历是前端机试出现频率最高的，代码可直接套用。

  3. 关键细节：JS中要注意null判断（二叉树大量空节点）、BST的中序递增特性、层序遍历的队列用法。

这些题目覆盖了前端机试中90%的二叉树考点，你可以把代码复制到本地运行，每道题手写2遍，确保机试时能快速写出。

（注：文档部分内容可能由 AI 生成）

最近更新