Skip to content

二叉树深度优先搜索

· 1 min

二叉树的搜索分为两种：

  1. 深度优先搜索
  2. 广度优先搜索

深度优先搜索

所谓深度优先搜索，顾名思义，就是先往下找，直到不能再往下了，再切换到平层的节点，切换到平层的节点后，继续往下进行搜索。

前序遍历，遍历的顺序为根节点 -> 左子树 -> 右子树

image-20250226092001455

前序遍历出来的顺序为：

A -> B -> D -> H -> I -> E -> J -> K -> C -> F -> L -> M -> G -> N -> O

深度优先搜索（Depth-First-Search，简称 DFS）也是按照这样的顺序。

代码实现：

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


// 初始化二叉树
const root = new TreeNode('A')
root.left = new TreeNode('B')
root.right = new TreeNode('C')
root.left.left = new TreeNode('D')
root.left.right = new TreeNode('E')
root.left.left.left = new TreeNode('H')
root.left.left.right = new TreeNode('I')
root.left.right.left = new TreeNode('J')
root.left.right.right = new TreeNode('K')
root.right.left = new TreeNode('F')
root.right.right = new TreeNode('G')
root.right.left.left = new TreeNode('L')
root.right.left.right = new TreeNode('M')
root.right.right.left = new TreeNode('N')
root.right.right.right = new TreeNode('O')


function depthFirstSearch(root, target) {
  if (root === null) return false


  if (root.value === target) return true


  const leftResult = depthFirstSearch(root.left, target)
  const rightResult = depthFirstSearch(root.right, target)


  return leftResult || rightResult
}
console.log(depthFirstSearch(root, 'J'))