Leetcode 919 Complete Binary Tree Inserter

发表于 |

完全二叉树是每一层（除最后一层外）都是完全填充（即，结点数达到最大）的，并且所有的结点都尽可能地集中在左侧。
设计一个用完全二叉树初始化的数据结构 CBTInserter，它支持以下几种操作：
CBTInserter(TreeNode root) 使用头结点为 root 的给定树初始化该数据结构；
CBTInserter.insert(int v) 将 TreeNode 插入到存在值为 node.val = v 的树中以使其保持完全二叉树的状态，并返回插入的 TreeNode 的父结点的值；
CBTInserter.get_root() 将返回树的头结点。

示例 1：
输入：inputs = [“CBTInserter”,”insert”,”get_root”], inputs = [[[1]],[2],[]]
输出：[null,1,[1,2]]

示例 2：
输入：inputs = [“CBTInserter”,”insert”,”insert”,”get_root”], inputs = [[[1,2,3,4,5,6]],[7],[8],[]]
输出：[null,3,4,[1,2,3,4,5,6,7,8]]

提示：

  1. 最初给定的树是完全二叉树，且包含 1 到 1000 个结点。
  2. 每个测试用例最多调用 CBTInserter.insert 操作 10000 次。
  3. 给定结点或插入结点的每个值都在 0 到 5000 之间。

题意分析：
构造一个完全二叉树，实现插入功能并返回父节点的值。

思路分析：
一说到完全二叉树我们就要想到其最基本的特性，如果将根结点的序号定义为1的话，则对于任意一个结点i，他的左孩子序号为2*i，右孩子序号为2*i+1，想到这一步就可做了。

我们始终使用一个数组保存每个结点，数组的下标即代表结点的序号。对于给定的初始化树，我们使用bfs方法获得初始数组（如果你对bfs算法不熟，可以参考这篇博客）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class CBTInserter(object):

    def __init__(self, root):
        self.rootnode = root # 始终保存根节点，为get_root函数使用
        self.node = [TreeNode(0)]# 初始化一个结点，使根结点在数组中序号为1
        Q = collections.deque([root])
        while Q:
            node = Q.popleft()
            self.node.append(node)
            if node.left: Q.append(node.left)
            if node.right: Q.append(node.right)

    def insert(self, v):
        node = TreeNode(v)
        index = len(self.node) // 2
        self.node.append(node)
        # 将结点插入到父节点下
        if not self.node[index].left:
            self.node[index].left = node
        else:
            self.node[index].right = node
        return self.node[index].val

    def get_root(self):
        return self.rootnode