leetcode用层级遍历数组导入二叉树的方法

导入例子

leetcode通常给一个层级遍历数组来导入二叉树
导入[1,2,2,3,4,4,3]

    1
   / \
  2   2
 / \ / \
3  4 4  3

导入 [1,2,2,null,3,null,3]

    1
   / \
  2   2
   \   \
   3    3

导入思路

只要数组第n个数不为nil，每个结点的左子树为2n+1，右子树为2n+2。
我们从数组第0个位置开始递归创建所有结点，并连接起来就可以。

导入代码

// 用递归的方法按层级遍历添加结点(没有的地方填-1)
func CreateNode(arr []int, pos int) *TreeNode {
    node := new(TreeNode)
    node.Val = arr[pos]
    if 2*pos+1 < len(arr) && arr[2*pos+1] != -1 {
        leftChild := CreateNode(arr, 2*pos+1)
        node.Left = leftChild
    }
    if 2*pos+2 < len(arr) && arr[2*pos+2] != -1 {
        rightChild := CreateNode(arr, 2*pos+2)
        node.Right = rightChild
    }
    return node
}

// 根据层级遍历数组生成二叉树
func CreateTree(arr []int) *TreeNode {
    if len(arr) == 0 {
        return nil
    }
    node := CreateNode(arr, 0)
    return node
}

附：python的导入方法

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Tree:
    def __init__(self, arr: list):
        self.CreateTree(arr)
        pass

    def CreateNode(self, arr: list, pos: int):
        node = TreeNode(arr[pos])
        if pos == 0:
            self.root = node
        if 2 * pos + 1 < len(arr) and arr[2 * pos + 1] != -1:
            leftChild = self.CreateNode(arr, 2 * pos + 1)
            node.left = leftChild
        if 2 * pos + 2 < len(arr) and arr[2 * pos + 2] != -1:
            rightChild = self.CreateNode(arr, 2 * pos + 2)
            node.right = rightChild
        return node # 重要

    def CreateTree(self, arr: list):
        if len(arr) == 0:
            return
        self.CreateNode(arr, 0)