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