博客

近期在LeetCode上刷树相关的题，LeetNode的二叉树的输入为一个列表，如下图。笔者平时习惯在本地编程调试正确后再提交，因此在本地调试时需要能将对应列表转化成二叉树的结构。

首先分析一下输入列表和对应二叉树的关系。实际上输入列表就是对对应二叉树的层序遍历，即逐层地，从左到右访问并输出所有节点，若对应位置无子节点则用 null 占位，详解如下图。

由于采用了 null 占位，输入序列可以看做是对一棵完全二叉树的层序遍历。因此输入序列将具有以下特性：

1.若序列不为空，则序列的第一个元素为对应二叉树的根节点

2.序列中，第

个元素为对应二叉树中第 k 层，从左向右第 i+1 个节点

因此可以通过维护一个队列 q 以将输入队列 l 转换成二叉树（返回二叉树的根节点）：

将列表l的第一个元素（即对应树的根节点）移除队列，生成根节点 root 并入队 q

While q不为空 do

q的第一个元素出队，记为节点 t

将列表l的下两个元素（若存在）移出队列 l，并生成节点 t 的左叶子节点和右叶子结

点，将对应叶子节点入队 q

End While

按上述方式处理时，队列 q 中节点的入队顺序和处理顺序均和层序遍历的顺序一致。因此可以满足：当任意节点入队 q 时，其左侧和上方(更低层)的节点均已入队；在取出并处理队列中任意节点 t 时，其同层节点均已在队 q 中(因为在处理更低层节点时已将和 t 同层的节入队 q)，队列l中下两个元素（若存在）即对应t的左右节点。

具体代码如下：

class TreeNode:
   """ 定义树的节点类型 """
    def __init__(self, val=None, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def makeTree(l:List) -> TreeNode:
    """ 由输入列表生成树，返回根节点 """
    q = []
    if not l:
        return
    root = TreeNode(val=l.pop(0))
    q.append(root)
    while q:
        t = q.pop(0)
        if l:
            if l[0] != 'null':
                t.left = TreeNode(val=l.pop(0))
                q.append(t.left)
            else:
                l.pop(0)
        if l:
            if l[0] != 'null':
                t.right = TreeNode(val=l.pop(0))
                q.append(t.right)
            else:
                l.pop(0)
    return root