LeetCode树类型题目：如何根据数组高效构建树？

高效构建LeetCode树：基于数组的实例化方法

LeetCode中许多树类型题目都要求根据给定数组构建二叉树。数组通常表示树的层次遍历结果。本文将探讨两种构建方法，并重点介绍高效的优化版本。

基础方法：递归构建

对于结构简单的树，递归构建是一种直观的方法。 然而，这种方法在处理大型数据集时效率较低。

var root = [1, 2, 5, 3, 4, null, 6];

function TreeNode(val, left, right) {
    this.val = (val === undefined ? 0 : val);
    this.left = (left === undefined ? null : left);
    this.right = (right === undefined ? null : right);
}

var tree = new TreeNode(1, null, null);
tree.left = new TreeNode(2, null, null);
tree.right = new TreeNode(5, null, null);
tree.left.left = new TreeNode(3, null, null);
tree.left.right = new TreeNode(4, null, null);
tree.right.right = new TreeNode(6, null, null);

优化方法：层序遍历构建

AI at Meta

Facebook 旗下的AI研究平台

下载

为了提高效率，尤其是在处理大型数组时，层序遍历构建法是更好的选择。它利用队列来管理节点，避免了递归的开销。

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;

  constructor(val: number) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function buildTree(data: (number | null)[]): TreeNode | null {
  if (!data.length || data[0] === null) return null;

  const root = new TreeNode(data[0]!);
  const queue: TreeNode[] = [root];
  let index = 1;

  while (queue.length && index < data.length) {
    const node = queue.shift()!;
    const leftVal = data[index++];
    const rightVal = data[index++];

    if (leftVal !== null) {
      node.left = new TreeNode(leftVal);
      queue.push(node.left);
    }
    if (rightVal !== null) {
      node.right = new TreeNode(rightVal);
      queue.push(node.right);
    }
  }

  return root;
}

这个优化版本使用队列来跟踪需要处理的节点，通过层序遍历的方式高效地构建二叉树。 它比递归方法更适合处理大规模输入数据。

通过选择合适的方法，我们可以根据数组高效地构建LeetCode树类型题目中的二叉树，从而提高代码效率和可读性。