跳到主要内容

树

数组转换为树​

/**
 * 扁平数据通过 parent 关联, 实现扁平结构转嵌套 tree 结构
input:

   [
      { name: '数据1', parent: null, id: 1 },
      { name: '数据2', id: 2, parent: 1 },
      { name: '数据3', parent: 2, id: 3 },
      { name: '数据4', parent: 3, id: 4 },
      { name: '数据5', parent: 4, id: 5 },
      { name: '数据6', parent: 2, id: 6 }
   ]

output:

   [
      {
         name: '数据1',
         parent: null,
         id: 1,
         children: [
            {
               name: '数据2',
               id: 2,
               parent: 1,
               children: [
                  {
                     name: '数据3',
                     parent: 2,
                     id: 3,
                     children: [
                        {
                           name: '数据4',
                           parent: 3,
                           id: 4,
                           children: [
                              {
                                 name: '数据5',
                                 parent: 4,
                                 id: 5,
                                 children: []
                              }
                           ]
                        }
                     ]
                  },
                  {
                     name: '数据6',
                     parent: 2,
                     id: 6,
                     children: []
                  }
               ]
            }
         ]
      }
   ]

 */
function listToTree (list) {

}
答案
function listToTree (list) {
  const map = {}
  const roots = []

  // 首先将每个节点按照 id 存入 map
  for (const item of list) {
    map[item.id] = { ...item, children: [] }
  }

  for (const item of list) {
    if (item.parent === null) {
      // 顶级节点
      roots.push(map[item.id])
    } else if (map[item.parent]) {
      // 非顶级节点，找到父节点并添加到其 children 数组中
      map[item.parent].children.push(map[item.id])
    }
  }

  return roots
}

module.exports = listToTree

Open browser consoleTests

深度遍历？​

答案
/**
 * 深度优先遍历
 */
function dfs (root) {
  // 深度优先遍历
  const res = []
  if (!root) return res
  const stack = [root]

  while (stack.length) {
    const node = stack.pop()
    res.push(node.value)
    if (node.children?.length) {
      // Add children in reverse order to maintain proper DFS traversal
      for (let i = node.children.length - 1; i >= 0; i--) {
        stack.push(node.children[i])
      }
    }
  }

  return res
}

module.exports = dfs

Open browser consoleTests

广度遍历？​

答案
/**
 * 广度优先遍历
 */
function bfs (root) {
  const res = []
  if (!root) return res
  const queue = [root]
  while (queue.length) {
    const node = queue.shift()
    res.push(node.value)
    if (node.children?.length) queue.push(...node.children)
  }
  return res
}

module.exports = bfs

Open browser consoleTests

树的先序,中序,后续?​

答案
/**
 * 先序遍历,
 * 1. 根节点
 * 2. 左子树
 * 3. 右子树
 */
function preOrderTree (tree) {
  // Check if tree is null or undefined
  if (!tree) return []

  let res = []
  res.push(tree.value)
  const leftTree = tree.left
  const rightTree = tree.right
  if (leftTree) {
    res = res.concat(preOrderTree(leftTree))
  }
  if (rightTree) {
    res = res.concat(preOrderTree(rightTree))
  }
  return res
}

/**
 * 中序遍历,
 * 1. 左子树
 * 2. 根节点
 * 3. 右子树
 */
function inOrderTree (tree) {
  // Check if tree is null or undefined
  if (!tree) return []

  let res = []
  const leftTree = tree.left
  const rightTree = tree.right
  if (leftTree) {
    res = res.concat(inOrderTree(leftTree))
  }
  res.push(tree.value)
  if (rightTree) {
    res = res.concat(inOrderTree(rightTree))
  }
  return res
}

/**
 * 后序遍历,
 * 1. 左子树
 * 2. 右子树
 * 3. 根节点
 */
function postOrderTree (tree) {
  // Check if tree is null or undefined
  if (!tree) return []

  let res = []
  const leftTree = tree.left
  const rightTree = tree.right
  if (leftTree) {
    res = res.concat(postOrderTree(leftTree))
  }
  if (rightTree) {
    res = res.concat(postOrderTree(rightTree))
  }
  res.push(tree.value)
  return res
}


module.exports = {
   preOrderTree,
   inOrderTree,
   postOrderTree
 }

Open browser consoleTests

二叉树的最大深度​

/**
 * 二叉树的最大深度
 * 输入：{value: 1}
 * 输出：1
 * 输入：{value: 1, left: {value: 2}, right: {value: 3}}
 * 输出：2
 * 输入：{value: 1, left: {value: 2, left: {value: 3, left: {value: 4}}}}
 * 输出：4
 */

function maxDepth (root) {

}
答案
/**
 * 二叉树的深度
 */
function maxDepth (root) {
  if (!root) return 0
  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
}

module.exports = maxDepth

Open browser consoleTests

翻转二叉树​

/**
 * 翻转二叉树
 * 输入：{value: 1, left: {value: 2}, right: {value: 3}}
 * 输出：{value: 1, left: {value: 3}, right: {value: 2}}
 * 输入：{value: 1, left: {value: 2, left: {value: 3}}, right: {value: 4}}
 * 输出：{value: 1, left: {value: 4}, right: {value: 2, right: {value: 3}}}
 */
function invertTree (root) {

}
答案
function invertTree (root) {
  if (!root) return
  const left = invertTree(root.left)
  const right = invertTree(root.right)
  root.left = right
  root.right = left
  return root
}

module.exports = invertTree

Open browser consoleTests

红黑树的平衡原理​

  • 特性：
    1. 节点是红色或黑色
    2. 根节点是黑色
    3. 所有叶子节点（NIL）是黑色
    4. 红色节点的子节点必须是黑色
    5. 从根到叶子的所有路径包含相同数量的黑色节点
  • 平衡手段：
    • 变色
    • 左旋
    • 右旋
  • 时间复杂度：O(logN)

B树和B+树的区别​

  • B树：
    • 所有节点都可以存储数据
    • 适合随机访问
    • 常用于文件系统
  • B+树：
    • 只有叶子节点存储数据
    • 叶子节点通过链表相连
    • 更适合范围查询
    • 常用于数据库索引

AVL树与红黑树比较​

  • AVL树：
    • 更严格的平衡（左右子树高度差不超过1）
    • 查询更快
    • 插入删除代价更大
  • 红黑树：
    • 平衡条件较宽松
    • 插入删除操作更快
    • 实际应用更广泛（如STL）

Trie树的应用场景​

  • 字符串快速检索
  • 前缀匹配
  • 自动补全
  • 拼写检查
  • IP路由表查找

208. 实现 Trie (前缀树)**​

  • 难度：中等
  • 考点：前缀树、字符串查找
  • 应用场景：搜索提示、自动完成

o(n)

class Trie {
  data: string[] = []

  insert (word: string): void {
    this.data.push(word)
  }

  search (word: string): boolean {
    return this.data.includes(word)
  }

  startsWith (prefix: string): boolean {
    return this.data.some(i => i.startsWith(prefix))
  }
}

o(1)

class TrieNode {
  // @ts-error
  // eslint-disable-next-line no-use-before-define
  children: Map<string, TrieNode> = new Map()
  isEndOfWord = false
}

class Trie {
  root: TrieNode = new TrieNode()

  insert (word: string): void {
    let currentNode = this.root
    for (const char of word) {
      if (!currentNode.children.has(char)) {
        currentNode.children.set(char, new TrieNode())
      }
      currentNode = currentNode.children.get(char)
    }
    currentNode.isEndOfWord = true
  }

  traverse (word: string): TrieNode | null {
    let currentNode = this.root
    for (const char of word) {
      if (!currentNode.children.has(char)) {
        return null
      }
      currentNode = currentNode.children.get(char)
    }
    return currentNode
  }

  search (word: string): boolean {
    const node = this.traverse(word)
    return node !== null && node.isEndOfWord
  }

  startsWith (prefix: string): boolean {
    const node = this.traverse(prefix)
    return node !== null
  }
}
22%