二叉树搜索的实现

问题

在二叉树中搜索指定的节点值，需要实现两种常见的搜索算法：

1. 深度优先搜索(DFS)：包括前序、中序、后序遍历
2. 广度优先搜索(BFS)：按层级遍历

给定一个二叉树和目标值，判断树中是否存在该值的节点。

解答

// 定义二叉树节点
class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

// 深度优先搜索 - 递归实现
function searchDFS(root, target) {
  // 基础情况：节点为空
  if (root === null) {
    return false;
  }
  
  // 找到目标值
  if (root.val === target) {
    return true;
  }
  
  // 递归搜索左子树和右子树
  return searchDFS(root.left, target) || searchDFS(root.right, target);
}

// 深度优先搜索 - 迭代实现（使用栈）
function searchDFSIterative(root, target) {
  if (root === null) {
    return false;
  }
  
  const stack = [root];
  
  while (stack.length > 0) {
    const node = stack.pop();
    
    // 找到目标值
    if (node.val === target) {
      return true;
    }
    
    // 先压入右子节点，再压入左子节点（保证左子树先被访问）
    if (node.right) {
      stack.push(node.right);
    }
    if (node.left) {
      stack.push(node.left);
    }
  }
  
  return false;
}

// 广度优先搜索 - 使用队列
function searchBFS(root, target) {
  if (root === null) {
    return false;
  }
  
  const queue = [root];
  
  while (queue.length > 0) {
    const node = queue.shift();
    
    // 找到目标值
    if (node.val === target) {
      return true;
    }
    
    // 将左右子节点加入队列
    if (node.left) {
      queue.push(node.left);
    }
    if (node.right) {
      queue.push(node.right);
    }
  }
  
  return false;
}

// 返回搜索路径的DFS实现
function searchPathDFS(root, target, path = []) {
  if (root === null) {
    return null;
  }
  
  // 将当前节点加入路径
  path.push(root.val);
  
  // 找到目标值，返回路径
  if (root.val === target) {
    return path;
  }
  
  // 在左子树中搜索
  const leftPath = searchPathDFS(root.left, target, [...path]);
  if (leftPath) {
    return leftPath;
  }
  
  // 在右子树中搜索
  const rightPath = searchPathDFS(root.right, target, [...path]);
  if (rightPath) {
    return rightPath;
  }
  
  return null;
}

使用示例

// 构建测试二叉树
//       1
//      / \
//     2   3
//    / \   \
//   4   5   6
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.right = new TreeNode(6);

// 测试深度优先搜索（递归）
console.log(searchDFS(root, 5));  // true
console.log(searchDFS(root, 7));  // false

// 测试深度优先搜索（迭代）
console.log(searchDFSIterative(root, 6));  // true
console.log(searchDFSIterative(root, 8));  // false

// 测试广度优先搜索
console.log(searchBFS(root, 3));  // true
console.log(searchBFS(root, 9));  // false

// 测试搜索路径
console.log(searchPathDFS(root, 5));  // [1, 2, 5]
console.log(searchPathDFS(root, 6));  // [1, 3, 6]
console.log(searchPathDFS(root, 7));  // null

// 性能对比示例
const startDFS = performance.now();
searchDFS(root, 6);
const endDFS = performance.now();
console.log(`DFS耗时: ${endDFS - startDFS}ms`);

const startBFS = performance.now();
searchBFS(root, 6);
const endBFS = performance.now();
console.log(`BFS耗时: ${endBFS - startBFS}ms`);

关键点

• 递归 vs 迭代：DFS可以用递归或栈实现，递归代码更简洁，但可能栈溢出；迭代使用显式栈，更可控
• DFS特点：空间复杂度O(h)，h为树高度；适合搜索深层节点或需要回溯的场景
• BFS特点：空间复杂度O(w)，w为树最大宽度；适合搜索浅层节点或需要层级信息的场景
• 时间复杂度：两种方法都是O(n)，n为节点总数，最坏情况需要遍历所有节点
• 提前终止：找到目标值后立即返回，避免不必要的遍历
• 路径记录：如需记录搜索路径，需要在递归过程中维护路径数组
• 边界处理：注意处理空树和空节点的情况
• 数据结构选择：DFS用栈（或递归调用栈），BFS用队列