往完全二叉树添加节点
# 📃 题目描述
题目链接:
- 剑指 Offer II 043. 往完全二叉树添加节点 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
- 完全二叉树插入器 - 完全二叉树插入器 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
# 🔔 解题思路
参数传进来的 root 就已经是完全二叉树了
我们只需要插入一个节点就行
很简单,直接用 list 存储完全二叉树的结果,插入节点直接放在 lsit 的最后面就行了。
新插入节点的父节点也很好算,根据下标来做:TreeNode parent = list.get(list.size() / 2 - 1);
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class CBTInserter {
private List<TreeNode> list;
// root 是个完全二叉树
// 层次遍历将结果存入 list
public CBTInserter(TreeNode root) {
this.list = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < queue.size(); i ++) {
TreeNode cur = queue.poll();
list.add(cur);
if (cur.left != null) {
queue.offer(cur.left);
}
if (cur.right != null) {
queue.offer(cur.right);
}
}
}
}
public int insert(int v) {
TreeNode newNode = new TreeNode(v);
list.add(newNode);
// newNode 的父节点
TreeNode parent = list.get(list.size() / 2 - 1);
// newNode 是左孩子
if (list.size() % 2 == 0) {
parent.left = newNode;
}
// newNode 是右孩子
else {
parent.right = newNode;
}
return parent.val;
}
public TreeNode get_root() {
return list.isEmpty() ? null : list.get(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();
*/
# 💥 复杂度分析
- 空间复杂度:
- 时间复杂度:
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10