【教3妹学算法-逐日3题(1)】完全二叉树插入器

藏宝库编辑 · 2024-10-9 12:01:58

插：前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，不由得分享一下给各人。点击跳转到网站。
坚固不拔，越积极越荣幸，各人一起学习鸭~~~

3妹：早啊， 2哥
2哥：3妹本日怎么这么开心
3妹：由于本日是周五啊，每个周五我都会很开心，由于明后天就不消上班了呀。
2哥：晚上去看影戏怎么样。
3妹：可以的，看笑剧片吗？
2哥：我无所谓，哪怕不看笑剧片，想到来日诰日不消上班，也能看出笑剧片的结果，哈哈。
3妹：ok, 晚上见，我要去上班啦。
2哥：别忘记通勤路上看看算法题，不能偷懒哈。

标题：

完全二叉树是每一层（除末了一层外）都是完全添补（即，节点数到达最大）的，而且全部的节点都尽大概地会合在左侧。
计划一种算法，将一个新节点插入到一个完备的二叉树中，并在插入后保持其完备。
实现 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]
提示：
树中节点数目范围为 [1, 1000]
0 <= Node.val <= 5000
root 是完全二叉树
0 <= val <= 5000
每个测试用例最多调用 insert 和 get_root 利用 10^4 次
思绪：

对于一棵完全二叉树而言，其除了末了一层之外都是完全添补的，而且末了一层的节点全部在最左侧。那么，只有倒数第二层（如果存在）最右侧的多少个节点，以及末了一层的全部节点可以再添加子节点，别的的节点都已经拥有两个子节点。
因此，我们可以利用一个队列存储上述提到的这些可以添加子节点的节点。队列中的存储次序为：起首「从左往右」存储倒数第二层最右侧的节点，再「从左往右」存储末了一层的全部节点。这一步可以利用广度优先搜索来完成，由于广度优先搜索就是按照层优先举行遍历的。
随后，当我们每次调用insert(val) 时，我们就创建出一个节点 child，并将它最为队列的队首节点的子节点。在这之后，我们需要把 child 加入队尾，而且如果对队首节点已经有两个子节点，我们需要将其从队列中移除。
java代码：

/** * 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 { Queue<TreeNode> candidate; TreeNode root; public CBTInserter(TreeNode root) {       this.candidate = new ArrayDeque<TreeNode>();       this.root = root;       Queue<TreeNode> queue = new ArrayDeque<TreeNode>();       queue.offer(root);       while (!queue.isEmpty()) {          TreeNode node = queue.poll();          if (node.left != null) {             queue.offer(node.left);          }          if (node.right != null) {             queue.offer(node.right);          }          if (!(node.left != null && node.right != null)) {             candidate.offer(node);          }       } } public int insert(int val) {       TreeNode child = new TreeNode(val);       TreeNode node = candidate.peek();       int ret = node.val;       if (node.left == null) {          node.left = child;       } else {          node.right = child;          candidate.poll();       }       candidate.offer(child);       return ret; } public TreeNode get_root() {       return root; }}/** * Your CBTInserter object will be instantiated and called as such: * CBTInserter obj = new CBTInserter(root); * int param_1 = obj.insert(val); * TreeNode param_2 = obj.get_root(); */

【教3妹学算法-逐日3题(1)】完全二叉树插入器

所属分类: 问答交流

新帖推荐: 30日

推荐作品