[LeetCode]Complete Binary Tree Inserter

这道题事实上就是考察树的分层遍历，因为complete binary tree就是按照每一层依次插入元素。这道题也是类似的，我们一直用vector动态地维护倒数第二层节点，这是所有处在还没有满层节点的父节点。我们还维护一个坐标表示当前层最左边的子节点还没有满的节点，随着我们插入，这个坐标一直右移，直到所有节点都有两个子节点了，我们移动到下层继续这个步骤。插入的时间复杂度平摊之后仍然是O(1)，因为我们对这一层所有的节点只遍历两次，一次在维护指正每次右移的时候，一次这层满了更新成下一层所有节点的时候。代码如下:

	class CBTInserter {
	public:
	CBTInserter(TreeNode* root) {
	if (!root)return;
	m_q.push_back(root);
	m_root = root;
	while (true)
	{
	vector<TreeNode*> tmp;
	int i = 0;
	while (i < m_q.size() && isFull(m_q[i]))
	{
	auto node = m_q[i++];
	tmp.push_back(node->left);
	tmp.push_back(node->right);
	}
	if (i < m_q.size()) { m_idx = i; break; }
	else m_q = tmp;
	}
	}
	int insert(int v) {
	auto node = new TreeNode(v);
	if (!m_root)
	{
	m_root = node;
	m_q.push_back(node);
	m_idx = 0;
	return m_root->val;
	}
	else
	{
	auto curr = m_q[m_idx];
	if (!curr->left)curr->left = node;
	else
	{
	curr->right = node;
	++m_idx;
	if (m_idx >= m_q.size())getNextLevel();
	}
	return curr->val;
	}
	}
	TreeNode* get_root() {
	return m_root;
	}
	private:
	TreeNode* m_root;
	vector<TreeNode*> m_q;
	int m_idx;
	bool isFull(TreeNode* root)
	{
	return root->left && root->right;
	}
	void getNextLevel()
	{
	vector<TreeNode*> nextLevel;
	for (const auto node : m_q)
	{
	nextLevel.push_back(node->left);
	nextLevel.push_back(node->right);
	}
	m_q = nextLevel;
	m_idx = 0;
	}
	};
	/**
	* 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();
	*/

view raw Complete Binary Tree Inserter.cpp hosted with ❤ by GitHub