題目難度: 中等

原題鏈接

今天繼續(xù)更新 Leetcode 的劍指 Offer（專項突擊版）系列, 大家在公眾號 算法精選 里回復(fù) 劍指offer2 就能看到該系列當(dāng)前連載的所有文章了, 記得關(guān)注哦~

題目描述

完全二叉樹是每一層（除最后一層外）都是完全填充（即，節(jié)點數(shù)達(dá)到最大，第 n 層有 2n-1 個節(jié)點）的，并且所有的節(jié)點都盡可能地集中在左側(cè)。

設(shè)計一個用完全二叉樹初始化的數(shù)據(jù)結(jié)構(gòu) CBTInserter，它支持以下幾種操作：

• CBTInserter(TreeNode root) 使用根節(jié)點為 root 的給定樹初始化該數(shù)據(jù)結(jié)構(gòu)；
• CBTInserter.insert(int v) 向樹中插入一個新節(jié)點，節(jié)點類型為 TreeNode，值為 v 。使樹保持完全二叉樹的狀態(tài)，并返回插入的新節(jié)點的父節(jié)點的值；
• CBTInserter.get_root() 將返回樹的根節(jié)點。

示例 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 到 1000 個節(jié)點。
• 每個測試用例最多調(diào)用 CBTInserter.insert 操作 10000 次。
• 給定節(jié)點或插入節(jié)點的每個值都在 0 到 5000 之間。

題目思考

1. 如何利用完全二叉樹的性質(zhì)?

解決方案

思路

• 分析題目, 為了保證插入新節(jié)點后仍保持完全二叉樹的狀態(tài), 我們需要知道當(dāng)前待插入的節(jié)點位置
• 根據(jù)完全二叉樹的性質(zhì), 這里有兩種可能:
  1. 當(dāng)前最底層還有空位, 則插入位置就是上個插入節(jié)點的相鄰右側(cè)
  2. 當(dāng)前最底層沒有空位了, 則需要往下新開辟一層, 并插入該層最左側(cè)
• 那如何判斷當(dāng)前最底層還有沒有空位呢?
  • 我們可以利用按層 BFS, 記錄最初給定的樹的每一層節(jié)點信息, 這樣就可以得到樹高度, 以及最底層的節(jié)點個數(shù)
  • 然后根據(jù)完全二叉樹的性質(zhì), 如果某層高度是 h(從 0 開始), 那么當(dāng)其節(jié)點個數(shù)達(dá)到 2^h 就表示這一層滿了, 否則就還有空位
  • 最后再按照上面的判斷, 就可以知道當(dāng)前待插入節(jié)點位置了
• 接下來我們需要得到待插入節(jié)點的父節(jié)點, 這里同樣可以利用完全二叉樹的性質(zhì): 某一層第 i 個節(jié)點的父節(jié)點一定是上一層第 i/2 個節(jié)點 (i 下標(biāo)從 0 開始)
• 舉兩個例子:
  1. 某一層第 0 個節(jié)點的左子節(jié)點是下一層第 0 個節(jié)點, 右子節(jié)點是下一層第 1 個節(jié)點
  2. 某一層第 2 個節(jié)點的左子節(jié)點是下一層第 4 個節(jié)點, 右子節(jié)點是下一層第 5 個節(jié)點
• 得到父節(jié)點之后, 我們判斷其左子節(jié)點是否為空, 是的話就說明待插入節(jié)點是其左子節(jié)點, 否則就是其右子節(jié)點
• 下面的代碼就對應(yīng)了上面的整個過程, 并且有詳細(xì)的注釋, 方便大家理解

復(fù)雜度

• 時間復(fù)雜度 O(1): 每次 insert 只需要幾個常數(shù)時間的操作
• 空間復(fù)雜度 O(N): 需要存儲所有節(jié)點到對應(yīng)的層

代碼

class CBTInserter:def __init__(self, root: TreeNode):self.root = rootself.levels = []q = [root]while q:curlen = len(q)for node in q[:curlen]:if node.left:q.append(node.left)if node.right:q.append(node.right)# 將當(dāng)前層加入levels列表self.levels.append(q[:curlen])q = q[curlen:]def insert(self, v: int) -> int:h = len(self.levels) - 1if len(self.levels[-1]) == 1 << h:# 最底層滿了, 需要新建一層self.levels.append([])# 父節(jié)點下標(biāo)是當(dāng)前待插入下標(biāo)除以2pi = len(self.levels[-1]) // 2# 父節(jié)點在倒數(shù)第二層, 根據(jù)其下標(biāo)得到父節(jié)點parent = self.levels[-2][pi]# 追加父子連接node = TreeNode(v)if not parent.left:# 父節(jié)點的左子節(jié)點還不存在, 將其指定為nodeparent.left = nodeelse:# 父節(jié)點的左子節(jié)點已存在, 將右子節(jié)點指定為nodeparent.right = node# 將node添加到最底層self.levels[-1].append(node)return parent.valdef get_root(self) -> TreeNode:return self.root

---

大家可以在下面這些地方找到我~😊

我的 GitHub

我的 Leetcode

我的 CSDN

我的知乎專欄

我的頭條號

我的?？途W(wǎng)博客

我的公眾號: 算法精選, 歡迎大家掃碼關(guān)注~😊