二叉树专题

二叉树题目核心：递归思维 + 遍历方式选择

📊 题目总览

题目	难度	梯队	关键技巧
前中后序遍历	⭐⭐⭐	第一梯队	递归/迭代
层序遍历	⭐⭐	基础	BFS队列
前序中序重构二叉树	⭐⭐⭐	第二梯队	哈希+递归
二叉树最大路径和	⭐⭐⭐	进阶	后序遍历
最近公共祖先	⭐⭐	基础	递归分治
序列化与反序列化	⭐⭐⭐	进阶	BFS/DFS

通用树节点定义

javascript

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

// 辅助函数：从数组创建二叉树（层序）
// 例如：[1, 2, 3, null, 4] 创建：
//       1
//      / \
//     2   3
//      \
//       4
function createTree(arr) {
  if (!arr.length || arr[0] === null) return null;
  
  const root = new TreeNode(arr[0]);
  const queue = [root];
  let i = 1;
  
  while (queue.length && i < arr.length) {
    const node = queue.shift();
    
    if (i < arr.length && arr[i] !== null) {
      node.left = new TreeNode(arr[i]);
      queue.push(node.left);
    }
    i++;
    
    if (i < arr.length && arr[i] !== null) {
      node.right = new TreeNode(arr[i]);
      queue.push(node.right);
    }
    i++;
  }
  
  return root;
}

1. 前中后序遍历

LeetCode: 144. 前序 / 94. 中序 / 145. 后序 | 梯队: 第一梯队 ✅

题目描述

给定二叉树根节点，返回其前序/中序/后序遍历结果。

前序: 根 → 左 → 右
中序: 左 → 根 → 右
后序: 左 → 右 → 根

代码实现 - 递归

javascript

// 前序遍历
function preorderRecursive(root, result = []) {
  if (!root) return result;
  result.push(root.val);          // 根
  preorderRecursive(root.left, result);   // 左
  preorderRecursive(root.right, result);  // 右
  return result;
}

// 中序遍历
function inorderRecursive(root, result = []) {
  if (!root) return result;
  inorderRecursive(root.left, result);    // 左
  result.push(root.val);                  // 根
  inorderRecursive(root.right, result);   // 右
  return result;
}

// 后序遍历
function postorderRecursive(root, result = []) {
  if (!root) return result;
  postorderRecursive(root.left, result);  // 左
  postorderRecursive(root.right, result); // 右
  result.push(root.val);                  // 根
  return result;
}

代码实现 - 迭代（重点掌握）

javascript

// 前序遍历 - 迭代
function preorderIterative(root) {
  const result = [];
  const stack = [];
  if (root) stack.push(root);

  while (stack.length) {
    const node = stack.pop();
    result.push(node.val);
    // 先右后左入栈，出栈顺序就是先左后右
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }

  return result;
}

// 中序遍历 - 迭代（最常考）
function inorderIterative(root) {
  const result = [];
  const stack = [];
  let curr = root;

  while (curr || stack.length) {
    // 一路向左
    while (curr) {
      stack.push(curr);
      curr = curr.left;
    }
    // 访问节点
    curr = stack.pop();
    result.push(curr.val);
    // 转向右子树
    curr = curr.right;
  }

  return result;
}

// 后序遍历 - 迭代（前序变形：根右左 → 反转 → 左右根）
function postorderIterative(root) {
  const result = [];
  const stack = [];
  if (root) stack.push(root);

  while (stack.length) {
    const node = stack.pop();
    result.push(node.val);
    // 先左后右入栈（与前序相反）
    if (node.left) stack.push(node.left);
    if (node.right) stack.push(node.right);
  }

  return result.reverse();
}

示例调用

javascript

//       1
//      / \
//     2   3
//    / \
//   4   5
const root = createTree([1, 2, 3, 4, 5]);

// 前序遍历
console.log(preorderIterative(root)); // [1, 2, 4, 5, 3]

// 中序遍历
console.log(inorderIterative(root));  // [4, 2, 5, 1, 3]

// 后序遍历
console.log(postorderIterative(root)); // [4, 5, 2, 3, 1]

// 边界条件：空树
console.log(preorderIterative(null));  // []

// 边界条件：单节点
console.log(inorderIterative(createTree([1]))); // [1]

// 边界条件：只有左子树
console.log(inorderIterative(createTree([1, 2, null, 3]))); // [3, 2, 1]

复杂度分析

时间: O(n)
空间: O(h)，h 为树高，最坏 O(n)

2. 层序遍历

LeetCode: 102. 二叉树的层序遍历 | 难度: 中等

题目描述

给定二叉树根节点，返回其按层遍历的节点值（逐层从左到右）。

代码实现

javascript

/**
 * 层序遍历 - BFS
 * @param {TreeNode} root
 * @return {number[][]}
 */
function levelOrder(root) {
  if (!root) return [];
  
  const result = [];
  const queue = [root];

  while (queue.length) {
    const level = [];
    const size = queue.length;

    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }

    result.push(level);
  }

  return result;
}

示例调用

javascript

//       3
//      / \
//     9  20
//       /  \
//      15   7
const root = createTree([3, 9, 20, null, null, 15, 7]);

console.log(levelOrder(root));
// 输出: [[3], [9, 20], [15, 7]]

// 边界条件：空树
console.log(levelOrder(null)); // []

// 边界条件：单节点
console.log(levelOrder(createTree([1]))); // [[1]]

// 边界条件：只有左子节点
console.log(levelOrder(createTree([1, 2]))); // [[1], [2]]

复杂度分析

时间: O(n)
空间: O(n) 队列最大宽度

3. 前序中序重构二叉树

LeetCode: 105. 从前序与中序遍历序列构造二叉树 | 梯队: 第二梯队

题目描述

给定两个整数数组 preorder 和 inorder，其中 preorder 是前序遍历，inorder 是中序遍历。构造并返回二叉树。

核心思路

前序：第一个元素是根节点
中序：根节点左边是左子树，右边是右子树
使用哈希表快速定位根节点在中序中的位置

代码实现

javascript

/**
 * 从前序和中序遍历构建二叉树
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
function buildTree(preorder, inorder) {
  // 哈希表存储中序遍历的索引
  const inorderMap = new Map();
  inorder.forEach((val, index) => inorderMap.set(val, index));

  let preIndex = 0;

  function build(inLeft, inRight) {
    if (inLeft > inRight) return null;

    // 前序遍历的第一个节点是根节点
    const rootVal = preorder[preIndex++];
    const root = new TreeNode(rootVal);

    // 在中序遍历中找到根节点位置
    const inIndex = inorderMap.get(rootVal);

    // 递归构建左右子树
    // 注意：必须先构建左子树，因为 preIndex 是自增的
    root.left = build(inLeft, inIndex - 1);
    root.right = build(inIndex + 1, inRight);

    return root;
  }

  return build(0, inorder.length - 1);
}

示例调用

javascript

// 基础示例
const preorder = [3, 9, 20, 15, 7];
const inorder = [9, 3, 15, 20, 7];
const tree = buildTree(preorder, inorder);
console.log(levelOrder(tree));
// 输出: [[3], [9, 20], [15, 7]]

// 边界条件：单节点
console.log(levelOrder(buildTree([1], [1]))); // [[1]]

// 边界条件：只有左子树
console.log(levelOrder(buildTree([1, 2], [2, 1]))); // [[1], [2]]

// 边界条件：只有右子树
console.log(levelOrder(buildTree([1, 2], [1, 2]))); // [[1], [2]]

// 边界条件：空数组
console.log(buildTree([], [])); // null

复杂度分析

时间: O(n)，哈希表查找 O(1)
空间: O(n)，哈希表 + 递归栈

4. 二叉树最大路径和

LeetCode: 124. 二叉树中的最大路径和 | 难度: 困难

可视化演示：点击查看算法动画

题目描述

路径被定义为从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。返回最大路径和。

核心思路

单边路径：只能往一个方向延伸，用于向上层返回
完整路径：可以包含左右子树，用于更新全局答案
负数贡献视为 0

代码实现

javascript

/**
 * 二叉树最大路径和
 * @param {TreeNode} root
 * @return {number}
 */
function maxPathSum(root) {
  let maxSum = -Infinity;

  function dfs(node) {
    if (!node) return 0;

    // 递归计算左右子树的最大贡献值（负数贡献视为 0）
    const leftMax = Math.max(0, dfs(node.left));
    const rightMax = Math.max(0, dfs(node.right));

    // 更新最大路径和（经过当前节点的完整路径）
    const pathSum = node.val + leftMax + rightMax;
    maxSum = Math.max(maxSum, pathSum);

    // 返回当前节点能贡献的最大单边路径和
    return node.val + Math.max(leftMax, rightMax);
  }

  dfs(root);
  return maxSum;
}

示例调用

javascript

//       -10
//       /  \
//      9   20
//         /  \
//        15   7
const root1 = createTree([-10, 9, 20, null, null, 15, 7]);
console.log(maxPathSum(root1)); // 42 (15 + 20 + 7)

// 简单示例
const root2 = createTree([1, 2, 3]);
console.log(maxPathSum(root2)); // 6 (2 + 1 + 3)

// 边界条件：单节点
console.log(maxPathSum(createTree([5]))); // 5

// 边界条件：全是负数
console.log(maxPathSum(createTree([-3]))); // -3

// 边界条件：包含负数
const root3 = createTree([2, -1]);
console.log(maxPathSum(root3)); // 2 (不选负数子节点)

复杂度分析

时间: O(n)
空间: O(h) 递归栈

5. 最近公共祖先(LCA)

LeetCode: 236. 二叉树的最近公共祖先 | 难度: 中等

题目描述

给定二叉树根节点和两个节点 p、q，找到它们的最近公共祖先。

核心思路

若 p 和 q 分别在 root 的左右子树 → root 是 LCA
若都在左子树 → 在左子树继续找
若都在右子树 → 在右子树继续找

代码实现

javascript

/**
 * 二叉树最近公共祖先
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
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;  // p 和 q 分别在左右子树
  return left || right;            // 都在同一侧
}

示例调用

javascript

//       3
//      / \
//     5   1
//    / \ / \
//   6  2 0  8
//     / \
//    7   4
const root = createTree([3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]);

// 手动获取节点引用（实际题目会给出）
const p = root.left;      // 节点 5
const q = root.right;     // 节点 1
console.log(lowestCommonAncestor(root, p, q).val); // 3

// p 和 q 在同一子树
const p2 = root.left;     // 节点 5
const q2 = root.left.right.right; // 节点 4
console.log(lowestCommonAncestor(root, p2, q2).val); // 5

// 边界条件：p 是 q 的祖先
console.log(lowestCommonAncestor(root, root, root.left).val); // 3

复杂度分析

时间: O(n)
空间: O(h) 递归栈

6. 序列化与反序列化

LeetCode: 297. 二叉树的序列化与反序列化 | 难度: 困难

可视化演示：点击查看算法动画

题目描述

设计一个算法将二叉树序列化为字符串，并能将该字符串反序列化为原来的树结构。

代码实现 - BFS

javascript

/**
 * 序列化二叉树 - BFS
 * @param {TreeNode} root
 * @return {string}
 */
function serialize(root) {
  if (!root) return '[]';
  
  const result = [];
  const queue = [root];
  
  while (queue.length) {
    const node = queue.shift();
    if (node) {
      result.push(node.val);
      queue.push(node.left);
      queue.push(node.right);
    } else {
      result.push(null);
    }
  }
  
  // 移除尾部的 null
  while (result[result.length - 1] === null) {
    result.pop();
  }
  
  return JSON.stringify(result);
}

/**
 * 反序列化二叉树 - BFS
 * @param {string} data
 * @return {TreeNode}
 */
function deserialize(data) {
  const arr = JSON.parse(data);
  if (!arr.length) return null;
  
  const root = new TreeNode(arr[0]);
  const queue = [root];
  let i = 1;
  
  while (queue.length && i < arr.length) {
    const node = queue.shift();
    
    if (i < arr.length && arr[i] !== null) {
      node.left = new TreeNode(arr[i]);
      queue.push(node.left);
    }
    i++;
    
    if (i < arr.length && arr[i] !== null) {
      node.right = new TreeNode(arr[i]);
      queue.push(node.right);
    }
    i++;
  }
  
  return root;
}

示例调用

javascript

const root = createTree([1, 2, 3, null, null, 4, 5]);

// 序列化
const serialized = serialize(root);
console.log(serialized); // "[1,2,3,null,null,4,5]"

// 反序列化
const tree = deserialize(serialized);
console.log(levelOrder(tree)); // [[1], [2, 3], [4, 5]]

// 边界条件：空树
console.log(serialize(null)); // "[]"
console.log(deserialize("[]")); // null

// 边界条件：单节点
console.log(serialize(new TreeNode(1))); // "[1]"

复杂度分析

时间: O(n)
空间: O(n)

💡 二叉树技巧总结

遍历方式	适用场景	时机
前序	统计节点、复制树	先处理根再处理子节点
中序	BST 操作、验证 BST	需要有序遍历
后序	删除节点、计算高度/路径	需要先知道子节点结果
层序	按层操作、最短路径	需要层级信息

javascript

// 二叉树递归模板
function dfs(node) {
  if (!node) return baseCase;
  
  // 前序位置：进入节点时处理
  const left = dfs(node.left);
  // 中序位置
  const right = dfs(node.right);
  // 后序位置：离开节点时处理
  
  return result;
}

二叉树专题 ​

📊 题目总览 ​

通用树节点定义 ​

1. 前中后序遍历 ​

题目描述 ​

代码实现 - 递归 ​

代码实现 - 迭代（重点掌握） ​

示例调用 ​

复杂度分析 ​

2. 层序遍历 ​

题目描述 ​

代码实现 ​

示例调用 ​

复杂度分析 ​

3. 前序中序重构二叉树 ​

题目描述 ​

核心思路 ​

代码实现 ​

示例调用 ​

复杂度分析 ​

4. 二叉树最大路径和 ​

题目描述 ​

核心思路 ​

代码实现 ​

示例调用 ​

复杂度分析 ​

5. 最近公共祖先(LCA) ​

题目描述 ​

核心思路 ​

代码实现 ​

示例调用 ​

复杂度分析 ​

6. 序列化与反序列化 ​

题目描述 ​

代码实现 - BFS ​

示例调用 ​

复杂度分析 ​

💡 二叉树技巧总结 ​

二叉树专题

📊 题目总览

通用树节点定义

1. 前中后序遍历

题目描述

代码实现 - 递归

代码实现 - 迭代（重点掌握）

示例调用

复杂度分析

2. 层序遍历

题目描述

代码实现

示例调用

复杂度分析

3. 前序中序重构二叉树

题目描述

核心思路

代码实现

示例调用

复杂度分析

4. 二叉树最大路径和

题目描述

核心思路

代码实现

示例调用

复杂度分析

5. 最近公共祖先(LCA)

题目描述

核心思路

代码实现

示例调用

复杂度分析

6. 序列化与反序列化

题目描述

代码实现 - BFS

示例调用

复杂度分析

💡 二叉树技巧总结