leetcode上tree树类型的题目，是怎么样根据数组实例化tree的，如下图和代码

Question

问题

leetcode上tree树类型的题目，是怎么样根据数组实例化tree的，如下图和代码

自己的想法

        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, 2, 5)
        tree.left = new TreeNode(2, 3, 4)
        tree.right = new TreeNode(5, null, 6)
        console.log('tree', tree);
        console.log('tree', JSON.stringify(tree));

疑问

有没有不像我这样写，代码一步到位实现的

Answer 1

数组中的内容为层序遍历的结果,其中如果只有一个子节点，则为下一层添加一个null以判断该节点唯一的子节点是左子节点还是右子节点

比如如下的树他的层序遍历的结果为

第一层: [1]
第二层: [2,5]
第三层: [3,4,null,6]
合并起来就是: [1,2,5,3,4,null,6]

更具层序遍历递推出树
数组当作队列使用时在数据量太大是可能会有性能问题，可自行更换

class TreeNode {
  val: number = 0
  left: TreeNode | null = null
  right: TreeNode | null = null

  constructor(val: number) {
    this.val = val
  }
}

const build = (data: (number | null)[]): TreeNode | null => {
  if (!data.length || data[0] === null) return null

  let ans
  let cur = (ans = new TreeNode(data[0]!))
  const parentQueue: TreeNode[] = []

  data.shift()
  parentQueue.push(cur)
  while (data.length) {
    const root = parentQueue.shift()!
    const left = data.shift()
    const right = data.shift()

    if (typeof left === 'number') {
      root.left = new TreeNode(left)
      parentQueue.push(root.left)
    }

    if (typeof right === 'number') {
      root.right = new TreeNode(right)
      parentQueue.push(root.right)
    }
  }

  return ans
}

Answer 2

之前在刷题的时候写了个Tree的一些辅助方法，希望能对你有所帮助！ 这里我只兼容了Integer类型，如有必要可以自行修改为泛型

  /** 通过数组构建链表 */
  public static TreeNode build(Integer[] data) {
    TreeNode[] nodes = new TreeNode[data.length];
    nodes[0] = new TreeNode(data[0]);

    for (int i = 1; i < data.length; i++) {
      if (data[i] == null) {
        continue;
      }
      // 计算父节点索引位置
      int parentNodeIndex = (i - 1) / 2;

      TreeNode node = new TreeNode(data[i]);
      nodes[i] = node;
      if (parentNodeIndex * 2 + 1 == i) {
        nodes[parentNodeIndex].left = node;
      } else {
        nodes[parentNodeIndex].right = node;
      }
    }
    return nodes[0];
  }