一、基础概念

1. 节点结构

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

2. 二叉树类型
   • 满二叉树：所有非叶子节点都有两个子节点
   • 完全二叉树：最后一层从左向右连续填充
   • 二叉搜索树（BST）：左子树所有节点 < 根 < 右子树所有节点
   • 平衡二叉树（AVL）：任意节点左右子树高度差 ≤1
   • 搜索二叉树（Search Binary Tree）：左子树所有节点 < 根 < 右子树所有节点

二、遍历方法

1. 深度优先（DFS）

// 前序遍历（根左右）
function preorder(root) {
    if (!root) return []
    return [root.val, ...preorder(root.left), ...preorder(root.right)]
}

// 迭代实现
function preOrderIterative(root) {
    const stack = [root],
        res = []
    while (stack.length) {
        const node = stack.pop()
        if (!node) continue
        res.push(node.val)
        stack.push(node.right) // 先右后左
        stack.push(node.left)
    }
    return res
}

2. 广度优先（BFS）

function levelOrder(root) {
    const queue = [root],
        res = []
    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)
        }
        res.push(level)
    }
    return res
}

3. 前序遍历（Preorder Traversal）

• 访问顺序：根节点 → 左子树 → 右子树
• 特点：先处理当前节点，再递归处理左右子树。
• 应用场景：复制树的结构、序列化二叉树（如 JSON 序列化）。
• 示例：对于二叉树：

      1
     / \
    2   3

前序遍历结果为： [1, 2, 3] 。

4. 中序遍历（Inorder Traversal）

• 访问顺序：左子树 → 根节点 → 右子树
• 特点：先处理左子树，再处理根节点，最后处理右子树。
• 应用场景：二叉搜索树（BST）的有序输出（升序排列）。
• 示例：对于二叉树：

      1
     / \
    2   3

中序遍历结果为： [2, 1, 3] 。

5. 后序遍历（Postorder Traversal）

• 访问顺序：左子树 → 右子树 → 根节点
• 特点：先处理左右子树，最后处理根节点。
• 应用场景：删除二叉树节点（需先删除子节点）、计算表达式树的值（如后缀表达式）。
• 示例：对于二叉树：

      1
     / \
    2   3

后序遍历结果为： [2, 3, 1] 。

前中后遍历对比

对比总结

遍历方式	根节点位置	典型应用场景
前序	最先访问根	复制树结构、序列化
中序	中间访问根	二叉搜索树的有序输出
后序	最后访问根	删除节点、表达式求值

示例详解 以更复杂的二叉树为例：

      1
     / \
    2   3
   / \
  4   5

• 前序遍历：[1, 2, 4, 5, 3]（根最先）
• 中序遍历：[4, 2, 5, 1, 3]（根在中间）
• 后序遍历：[4, 5, 2, 3, 1]（根最后）

实现核心差异

• 递归法：调整递归函数中访问根节点的位置。
• 迭代法：
  • 前序：用栈，按根→右→左顺序压栈（弹出时顺序为根→左→右）。
  • 中序：用栈和指针，先压左到底，再退栈访问根，最后处理右。
  • 后序：用双栈或逆序操作，按根→右→左压栈，最后反转结果（结果为左→右→根）。

三、前端应用场景

1. UI组件树操作

   • 递归渲染嵌套组件（如树形菜单）
   • 虚拟DOM的diff算法（React/Vue）

2. 路由配置管理

   • 扁平化路由表转树形结构
   • 嵌套路由权限校验

3. 数据可视化

   • 组织树状图布局（D3.js）
   • 思维导图节点关系维护

4. 状态管理

   • Redux状态树的时间旅行调试
   • 撤销/重做操作的快照存储

四、高频算法题（前端向）

1. 基础操作

// 求二叉树深度
function maxDepth(root) {
    return root ? 1 + Math.max(maxDepth(root.left), maxDepth(root.right)) : 0
}

// 判断对称二叉树
function isSymmetric(root) {
    function compare(left, right) {
        if (!left && !right) return true
        if (!left || !right) return false
        return left.val === right.val &&
            compare(left.left, right.right) &&
            compare(left.right, right.left)
    }
    return compare(root.left, root.right)
}

2. 路径问题

// 路径总和（是否存在路径和等于target）
function hasPathSum(root, target) {
    if (!root) return false
    if (!root.left && !root.right) return root.val === target
    return hasPathSum(root.left, target - root.val) ||
        hasPathSum(root.right, target - root.val)
}

五、性能优化要点

1. 递归优化

   • 尾递归优化（JavaScript引擎支持有限）
   • 迭代替代深度递归（防止栈溢出）

2. 大数据处理

   • 分治策略：处理超大树时拆分子树
   • 记忆化缓存：存储已计算的子树结果

3. 存储优化

   • 数组存储完全二叉树（索引计算：父i → 左2i+1，右2i+2）
   • 结构序列化（JSON → 嵌套对象结构）

六、工具与调试

1. 可视化工具

   • BST Visualization（在线二叉树生成器）
   • React Family Tree（组件树可视化）

2. 调试技巧

// 打印树结构
function printTree(root, prefix = "", isLeft = true) {
    if (!root) return
    console.log(prefix + (isLeft ? "├── " : "└── ") + root.val)
    printTree(root.left, prefix + (isLeft ? "│   " : "    "), true)
    printTree(root.right, prefix + (isLeft ? "│   " : "    "), false)
}

七、学习资源

1. LeetCode经典题

   • 94/144/145（三种DFS遍历）
   • 102（层序遍历）
   • 105（前序+中序构建树）

2. 实战项目

   • 实现JSON数据差异对比工具
   • 开发可折叠树形菜单组件
   • 构建递归式路由配置解析器