LeetCode: Populating Next Right Pointers in Each Node II 解题报告
2024-10-15 05:43:49
Populating Next Right Pointers in Each Node II
Follow up for problem "Populating Next Right Pointers in Each Node".
What if the given tree could be any binary tree? Would your previous solution still work?
Note:
You may only use constant extra space.
For example,
Given the following binary tree,
1
/ \
2 3
/ \ \
4 5 7
After calling your function, the tree should look like:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ \
4-> 5 -> 7 -> NULL
SOLUTION 1
本题还是可以用Level Traversal 轻松解出，连代码都可以跟上一个题目一模一样。Populating Next Right Pointers in Each Node Total
但是不符合空间复杂度的要求：constant extra space.
时间复杂度： O(N)
/**
* Definition for binary tree with next pointer.
* public class TreeLinkNode {
* int val;
* TreeLinkNode left, right, next;
* TreeLinkNode(int x) { val = x; }
* }
*/
public class Solution {
public void connect(TreeLinkNode root) {
if (root == null) {
return;
} TreeLinkNode dummy = new TreeLinkNode(0);
Queue<TreeLinkNode> q = new LinkedList<TreeLinkNode>(); q.offer(root);
q.offer(dummy); while(!q.isEmpty()) {
TreeLinkNode cur = q.poll();
if (cur == dummy) {
if (!q.isEmpty()) {
q.offer(dummy);
}
continue;
} if (q.peek() == dummy) {
cur.next = null;
} else {
cur.next = q.peek();
} if (cur.left != null) {
q.offer(cur.left);
} if (cur.right != null) {
q.offer(cur.right);
}
} }
}
SOLUTION 2
我们可以用递归解出。注意从右往左加next。否则的话 右边未建立，左边你没找不到next. Space Complexity:
时间复杂度： O(N)
public void connect(TreeLinkNode root) {
if (root == null) {
return;
}
TreeLinkNode cur = root.next;
TreeLinkNode next = null;
// this is very important. should exit after found the next.
while (cur != null && next == null) {
if (cur.left != null) {
next = cur.left;
} else if (cur.right != null) {
next = cur.right;
} else {
cur = cur.next;
}
}
if (root.right != null) {
root.right.next = next;
next = root.right;
}
if (root.left != null) {
root.left.next = next;
}
// The order is very important. We should deal with right first!
connect(root.right);
connect(root.left);
}
2014.1229 redo:
但现在leetcode加强数据了，不管怎么优化，递归的版本再也不能通过，都TLE
// SOLUTION 2: REC
public void connect(TreeLinkNode root) {
if (root == null) {
return;
} TreeLinkNode dummy = new TreeLinkNode(0);
TreeLinkNode pre = dummy; if (root.left != null) {
pre.next = root.left;
pre = root.left;
} if (root.right != null) {
pre.right = root.right;
pre = root.right;
} if (root.left == null && root.right == null) {
return;
} // Try to find the next node;
TreeLinkNode cur = root.next;
TreeLinkNode next = null;
while (cur != null) {
if (cur.left != null) {
next = cur.left;
break;
} else if (cur.right != null) {
next = cur.right;
break;
} else {
cur = cur.next;
}
} pre.next = next; if (root.right != null && (root.right.left != null || root.right.right != null)) {
connect(root.right);
} if (root.left != null && (root.left.left != null || root.left.right != null)) {
connect(root.left);
} }
SOLUTION 3
我们可以用Iterator 直接解出。并且不开辟额外的空间，也就是说空间复杂度是 O（1）
时间复杂度： O(N)
感谢 http://www.geeksforgeeks.org/connect-nodes-at-same-level-with-o1-extra-space/ 的作者
/*
Solution 3: iterator with O(1) space.
*/
public void connect(TreeLinkNode root) {
if (root == null) {
return;
} connIterator(root);
} /*
This is a iterator version.
*/
public void connIterator(TreeLinkNode root) {
TreeLinkNode leftEnd = root;
while (leftEnd != null) {
TreeLinkNode p = leftEnd; // Connect all the nodes in the next level together.
while (p != null) { // find the
TreeLinkNode next = findLeftEnd(p.next); if (p.right != null) {
p.right.next = next;
next = p.right;
} if (p.left != null) {
p.left.next = next;
} // continue to deal with the next point.
p = p.next;
} // Find the left end of the NEXT LEVEL.
leftEnd = findLeftEnd(leftEnd);
} } // Find out the left end of the next level of Root TreeNode.
public TreeLinkNode findLeftEnd(TreeLinkNode root) {
while (root != null) {
if (root.left != null) {
return root.left;
} if (root.right != null) {
return root.right;
} root = root.next;
} return null;
}
SOLUTION 4 (2014.1229):
在sol3基础上改进，引入dummynode，我们就不需要先找到最左边的点了。空间复杂度是 O（1）时间复杂度： O(N)
// SOLUTION 1: Iteration
public void connect1(TreeLinkNode root) {
if (root == null) {
return;
} TreeLinkNode leftEnd = root; // Bug 1: don't need " && leftEnd.left != null"
while (leftEnd != null) {
TreeLinkNode cur = leftEnd; TreeLinkNode dummy = new TreeLinkNode(0);
TreeLinkNode pre = dummy;
while (cur != null) {
if (cur.left != null) {
pre.next = cur.left;
pre = cur.left;
} if (cur.right != null) {
pre.next = cur.right;
pre = cur.right;
} cur = cur.next;
}
leftEnd = dummy.next;
}
}
CODE ON GITHUB:
https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/tree/Connect2_2014_1229.java
最新文章
- DS 工作室
- 【Java EE 学习 80 下】【调用WebService服务的四种方式】【WebService中的注解】
- python 字符串编码转换
- eclipse安装svn和maven插件以及m2e-extras
- Win8 app判断网络连接状态
- Collection与Map
- CSS+JS实现兼容性很好的无限级下拉菜单
- liunx命令之whereis、which、find的区别和联系
- JAVA学习第五十九课 — 网络编程概述
- 学习SQL关联查询
- php basename()文件夹 路径 文件后缀名 读取pathinfo()
- JQ实战天猫淘宝放大镜
- “海市蜃楼”般的逛街体验——VR全景智慧城市常诚
- 使用TP5创建一个REST API
- GO语言标准库—命令行参数解析FLAG
- UVa 11300 分金币
- Linux Framebuffer save as picture
- ant批量运行Jmeter脚本遇到 Content is not allowed in prolog.问题及解决方案
- Linux下编写 makefile 详细教程
- [修正] Firemonkey 中英文混排折行，省略字符，首字避开标点
热门文章
- javaweb项目打成war包
- 〖Linux〗Ubuntu 64位安装sqlite3_analyzer
- 调用网易有道词典api
- 学习KNN
- Python 实现的、带GUI界面的词云生成器
- 利用Windows 2003系统中实现两个网段的路由
- 有效Log4j按指定级别定向输出日志到指定的输出文件地址配置Threshold，log4j中如何屏蔽父logger输出源rootlogger的additivity配置，log4j向多个文件记录日志
- 手机网络抓包 转载记录http://blog.csdn.net/skylin19840101/article/details/43485911
- 采用异步来实现重新连接服务器或者重新启动服务 C#中类的属性的获取 SignalR2简易数据看板演示 C#动态调用泛型类、泛型方法 asp .net core Get raw request. 从壹开始前后端分离[.NetCore 不定期更新] 38 ║自动初始化数据库
- 浅谈 .NET 中的对象引用、非托管指针和托管指针