題目描述
這是 LeetCode 上的 919. 完全二叉樹插入器 ,難度為 中等。
Tag : 「模拟」、「BFS」、「樹的周遊」
完全二叉樹 是每一層(除最後一層外)都是完全填充(即,節點數達到最大)的,并且所有的節點都盡可能地集中在左側。
設計一種算法,将一個新節點插入到一個完整的二叉樹中,并在插入後保持其完整。
實作
CBTInserter
類:
-
使用頭節點為CBTInserter(TreeNode root)
的給定樹初始化該資料結構;root
-
向樹中插入一個值為CBTInserter.insert(int v)
的新節點Node.val == val
。使樹保持完全二叉樹的狀态,并傳回插入節點TreeNode
的父節點的值TreeNode
-
将傳回樹的頭節點。CBTInserter.get_root()
示例 1:
輸入
["CBTInserter", "insert", "insert", "get_root"]
[[[1, 2]], [3], [4], []]
輸出
[null, 1, 2, [1, 2, 3, 4]]
解釋
CBTInserter cBTInserter = new CBTInserter([1, 2]);
cBTInserter.insert(3); // 傳回 1
cBTInserter.insert(4); // 傳回 2
cBTInserter.get_root(); // 傳回 [1, 2, 3, 4]
提示:
- 樹中節點數量範圍為
-
是完全二叉樹root
- 每個測試用例最多調用
和insert
操作get_root
BFS
起始使用數組對構造函數傳入的
root
進行
BFS
層序周遊(由于仍要保留層序周遊順序,是以使用下标指針
cur
來模拟出隊位置)。
對于
insert
操作而言,我們要在數組(層序周遊順序)中找到首個「存在左右空子節點」的父節點
fa
,由于找到
fa
節點的過程數組下标單調遞增,是以可以使用全局變量
idx
不斷往後搜尋,每次将新節點
node
添加到目前樹後,需要将
node
添加到數組尾部。
get_root
操作則始終傳回數組首位元素即可。
Java 代碼:
class CBTInserter {
List<TreeNode> list = new ArrayList<>();
int idx = 0;
public CBTInserter(TreeNode root) {
list.add(root);
int cur = 0;
while (cur < list.size()) {
TreeNode node = list.get(cur);
if (node.left != null) list.add(node.left);
if (node.right != null) list.add(node.right);
cur++;
}
}
public int insert(int {
TreeNode node = new TreeNode(val);
while (list.get(idx).left != null && list.get(idx).right != null) idx++;
TreeNode fa = list.get(idx);
if (fa.left == null) fa.left = node;
else if (fa.right == null) fa.right = node;
list.add(node);
return fa.val;
}
public TreeNode get_root() {
return list.get(0);
}
}
TypeScript 代碼:
class CBTInserter {
list: TreeNode[] = new Array<TreeNode>()
idx: number = 0
constructor(root: TreeNode | null) {
this.list.push(root)
let cur = 0
while (cur < this.list.length) {
const node = this.list[cur]
if (node.left != null) this.list.push(node.left)
if (node.right != null) this.list.push(node.right)
cur++
}
}
insert(val: number): number {
const node = new TreeNode(val)
while (this.list[this.idx].left != null && this.list[this.idx].right != null) this.idx++
const fa = this.list[this.idx]
if (fa.left == null) fa.left = node
else if (fa.right == null) fa.right = node
this.list.push(node)
return fa.val
}
get_root(): TreeNode | null {
return this.list[0]
}
}
- 時間複雜度:
- 空間複雜度:
最後
這是我們「刷穿 LeetCode」系列文章的第
No.919
篇,系列開始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道題目,部分是有鎖題,我們将先把所有不帶鎖的題目刷完。