0919._Complete_Binary_Tree_Inserter.md

919. Complete Binary Tree Inserter

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/complete-binary-tree-inserter/description/

内容描述

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

Write a data structure CBTInserter that is initialized with a complete binary tree and supports the following operations:

CBTInserter(TreeNode root) initializes the data structure on a given tree with head node root;
CBTInserter.insert(int v) will insert a TreeNode into the tree with value node.val = v so that the tree remains complete, and returns the value of the parent of the inserted TreeNode;
CBTInserter.get_root() will return the head node of the tree.
 

Example 1:

Input: inputs = ["CBTInserter","insert","get_root"], inputs = [[[1]],[2],[]]
Output: [null,1,[1,2]]
Example 2:

Input: inputs = ["CBTInserter","insert","insert","get_root"], inputs = [[[1,2,3,4,5,6]],[7],[8],[]]
Output: [null,3,4,[1,2,3,4,5,6,7,8]]
 

Note:

The initial given tree is complete and contains between 1 and 1000 nodes.
CBTInserter.insert is called at most 10000 times per test case.
Every value of a given or inserted node is between 0 and 5000.

解题方案

思路 1 - 时间复杂度: O(1)- 空间复杂度: O(N)******

• init的时候来个层序遍历搞起来，两个列表一个按照次序放node，一个按照次序放对应的value
• 每次插入的时候先得到父亲的index，然后如果插入后总node数为偶数就说明是右孩子，反之则是左孩子
• get_root则简单了，直接返回self.lst[0]

class CBTInserter(object):

    def __init__(self, root):
        """
        :type root: TreeNode
        """
        self.lst = []
        self.values = []
        def levelTraversal(root):
            cur_level = [root]
            while cur_level:
                next_level = []
                for node in cur_level:
                    if node.left:
                        next_level.append(node.left)
                    if node.right:
                        next_level.append(node.right)
                    self.lst.append(node)
                    self.values.append(node.val)
                    cur_level = next_level
        levelTraversal(root)

        

    def insert(self, v):
        """
        :type v: int
        :rtype: int
        """
        self.values.append(v)
        self.lst.append(TreeNode(v))
        idx = len(self.lst) - 1
        if idx & 1:
            self.lst[(idx-1)//2].left = self.lst[-1]
        else:
            self.lst[(idx-1)//2].right = self.lst[-1]
        return self.values[(idx-1)//2] if idx > 0 else self.values[0]
        

    def get_root(self):
        """
        :rtype: TreeNode
        """
        return self.lst[0]
        


# Your CBTInserter object will be instantiated and called as such:
# obj = CBTInserter(root)
# param_1 = obj.insert(v)
# param_2 = obj.get_root()