leetcode-填充同一层的兄弟节点Ⅱ
2024-08-28 14:54:44
给定一个二叉树
struct TreeLinkNode {
TreeLinkNode *left;
TreeLinkNode *right;
TreeLinkNode *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
说明:
- 你只能使用额外常数空间。
- 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
示例:
给定二叉树，
1
/ \
2 3
/ \ \
4 5 7
调用你的函数后，该二叉树变为：
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ \
4-> 5 -> 7 -> NULL
第一道题是：leetcode-每个节点的右向指针（填充同一层的兄弟节点）
我们依然可以使用层序遍历的方法，为每个结点添加next指针。
但是时间复杂度不满足要求。
public class Solution {
public void connect(TreeLinkNode root) {
if(root==null)return ;
Queue<TreeLinkNode> q=new LinkedList();
q.add(root);
while(!q.isEmpty()){
int size=q.size();
for(int i=;i<size;i++){
TreeLinkNode temp=q.peek();q.poll();
if(i<size-)temp.next=q.peek();
if(temp.left!=null)q.add(temp.left);
if(temp.right!=null)q.add(temp.right);
}
}
}
将第一题的递归方法进行改造：
比如该二叉树
1
/ \
2 3
/ \ \
4 5 7
\ / \
9 14 15
/ \
18 19
遍历的顺序为：14->15 2->3 5->7 4->5 9->14 18->19
每次先处理结点的右子树，递归到叶子结点（没有左子树和右子树）。然后返回上一层，递归处理左子树。
类似于前序遍历的镜像： trave(root.right) ;
trave(root.left);
对每一层结点的处理可以通过tem=tem.next来进行跳转。
得到如下方法：
public class Solution {
public void connect(TreeLinkNode root) {
if(root==null)return;
TreeLinkNode tem=root;
//处理root左子树的指针
if(root.left!=null){
if(root.right!=null){
root.left.next=root.right;
}
//处理root.left.next的指向
while(tem.next!=null&&root.left.next==null){
tem=tem.next;//tem可以在同一层结点进行跳转
if(tem.left!=null)root.left.next=tem.left;
else if(tem.right!=null)root.left.next=tem.right;
}
}
//处理root右子树的指针
if(root.right!=null){
//处理root.right.next的指向
while(tem.next!=null&&root.right.next==null){
tem=tem.next;//tem可以在同一层结点进行跳转
if(tem.left!=null)root.right.next=tem.left;
else if(tem.right!=null)root.right.next=tem.right;
}
}
connect(root.right);
connect(root.left);
}
}
结果： 执行用时: 1 ms, 在Populating Next Right Pointers in Each Node II的Java提交中击败了98.04% 的用户
最新文章
- PHP eof的使用
- ProFTPD <=1.3.5 mod_copy 未授权文件复制漏洞
- outlook——还原“未读邮件”文件夹
- libdispatch for Linux
- Ztree使用笔记
- VC++ 文件系统
- SET ? DECLARE
- PostgreSQL的 initdb 源代码分析之四
- yuv 图像里的stride和plane的解释
- （转载）使用JavaScript操作表单
- 如何在 CentOS 7 上安装 Redis 服务器
- python编码错误
- 关于php中，记录日志中，将数组转为json信息记录日志时遇到的问题总结
- Flask 扩展 Mail
- 禁用 Chrome 的黑色模式/Dark Mode
- centos7 安装php gd库
- zookeeper的可视化web界面
- Gradle with Android
- 长城小主机GW1等型号进BIOS的设置方法
- RHCSA和RHCE