本文共 3560 字，大约阅读时间需要 11 分钟。

题目：

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 treeremains 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 1000nodes.

CBTInserter.insert is called at most 10000 times per test case.

Every value of a given or inserted node is between 0 and 5000.

解释：

# Definition for a binary tree node.# class TreeNode(object):#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass CBTInserter(object):    def __init__(self, root):        """        :type root: TreeNode        """        self.root=root        #层序遍历找到父节点        self.queue=[]        self.queue.append(root)        while True:            front=self.queue[0]            if not front.left:                break            self.queue.append(front.left)            if not front.right:                break            self.queue.append(front.right)            self.queue.pop(0)            def insert(self, v):        """        :type v: int        :rtype: int        """        tmpnode=TreeNode(v)        parent=self.queue[0]        if not parent.left:            parent.left=tmpnode        else:            parent.right=tmpnode            self.queue.pop(0)        self.queue.append(tmpnode)        return parent.val            def get_root(self):        """        :rtype: TreeNode        """        return self.root        # Your CBTInserter object will be instantiated and called as such:# obj = CBTInserter(root)# param_1 = obj.insert(v)# param_2 = obj.get_root()

c++代码：

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class CBTInserter {
   public:    TreeNode* global_root;    queue
   
     _queue;    CBTInserter(TreeNode* root) {
           global_root=root;        _queue.push(root);        while(true)        {
               TreeNode* tmp=_queue.front();            if(! tmp->left)                break;            _queue.push(tmp->left);            if(!tmp->right)                break;            _queue.push(tmp->right);            _queue.pop();        }    }        int insert(int v) {
           TreeNode* parent=_queue.front();        TreeNode* tmpNode=new TreeNode(v);        if(!parent->left)            parent->left=tmpNode;        else        {
               parent->right=tmpNode;            _queue.pop();        }        _queue.push(tmpNode);        return parent->val;    }        TreeNode* get_root() {
           return global_root;    }};/** * Your CBTInserter object will be instantiated and called as such: * CBTInserter obj = new CBTInserter(root); * int param_1 = obj.insert(v); * TreeNode* param_2 = obj.get_root(); */
   

总结：

转载地址：http://jrlcn.baihongyu.com/