PopulatingNextRightPointersInEachNodeII [source code]
public class PopulatingNextRightPointersInEachNodeII {
static
/******************************************************************************/
public class Solution {
public void connect(TreeLinkNode root) {
if (root == null)
return;
TreeLinkNode cur_head = root;
while (cur_head != null) {
TreeLinkNode cur_prev = null, cur_node = cur_head, next_prev = null, next_head = null;
while (cur_node != null) {
if (next_head == null && (cur_node.left != null || cur_node.right != null))
next_head = cur_node.left != null ? cur_node.left : cur_node.right;
if (cur_node.left != null && cur_node.right != null) {
if (next_prev != null)
next_prev.next = cur_node.left;
cur_node.left.next = cur_node.right;
next_prev = cur_node.right;
} else if (cur_node.left != null) {
if (next_prev != null)
next_prev.next = cur_node.left;
next_prev = cur_node.left;
} else if (cur_node.right != null) {
if (next_prev != null)
next_prev.next = cur_node.right;
next_prev = cur_node.right;
}
cur_prev = cur_node;
cur_node = cur_node.next;
}
cur_head = next_head;
}
}
}
/******************************************************************************/
public static void main(String[] args) {
PopulatingNextRightPointersInEachNodeII.Solution tester = new PopulatingNextRightPointersInEachNodeII.Solution();
int k = 1;
int[][] inputs = {
{1,2,3,4,5,-1,7},
{1,2,3,4,5,-1,7,-1,-1,-1,6,-1,9},
};
for (int i = 0; i < inputs.length / k; i++) {
System.out.println (Printer.separator ());
TreeLinkNode root = TreeLinkNode.bfsBuild (inputs[k * i]);
tester.connect (root);
System.out.printf ("%s\n -> \n%s\n",
TreeLinkNode.serialize (root), checkNext (root)
);
}
}
static String checkNext (TreeLinkNode root) {
StringBuilder sb = new StringBuilder ();
Queue<TreeLinkNode> queue = new LinkedList<> ();
queue.offer (root);
while (!queue.isEmpty ()) {
int size = queue.size ();
for (int i = 0; i < size; i++) {
TreeLinkNode cur = queue.poll ();
sb.append (String.format ("%d -> %s", cur.val, cur.next != null ? cur.next.val + "" : "null"));
if (cur.left != null)
queue.offer (cur.left);
if (cur.right != null)
queue.offer (cur.right);
if (!queue.isEmpty ())
sb.append ("\n");
}
}
return sb.toString ();
}
}
我感觉我之前那个办法应该还是可以的啊; 这个真的是无所谓的;
不对, 我之前的方法, 依赖一个走left beam的过程, 假如是一个没有left beam的, 怎么办?
好像稍微改一下并不难的样子, 左边大梁只要是有left尽量走left, 没有left的时候就走right就行了;
那就不废话, 开始写; 写的过程中发现, 用我之前那个方法好像有点问题, 比如假如当前level是2 3 4, 然后2和4都正常有child, 但是3一个child都没有怎么办? 你怎么在这一level处理连自己的children们?
进一步想了一下, 好像最好在head这个level和child这个level都用带prev的traversal才好呢;
对于cur_node的处理刚开始想要想到什么整合的做法, 不过后来想想还是算了, 就枚举算了, 做出来才是最狠的; 实在不行写完再整理到一起都可以;
这题居然也有Null input的case; 算了, 这种自定义结构作为输入的好像还是很容易玩这一招;
一开始写了这样一个代码:
public void connect(TreeLinkNode root) {
if (root == null)
return;
TreeLinkNode cur_head = root, next_head = null;
while (cur_head.left != null || cur_head.right != null) {
next_head = cur_head.left != null ? cur_head.left : cur_head.right;
TreeLinkNode cur_prev = null, cur_node = cur_head, dummy = new TreeLinkNode (0), next_prev = dummy;
dummy.next = next_head;
while (cur_node != null) {
if (cur_node.left != null && cur_node.right != null) {
if (next_prev != null)
next_prev.next = cur_node.left;
cur_node.left.next = cur_node.right;
next_prev = cur_node.right;
} else if (cur_node.left != null) {
if (next_prev != null)
next_prev.next = cur_node.left;
next_prev = cur_node.left;
} else if (cur_node.right != null) {
if (next_prev != null)
next_prev.next = cur_node.right;
next_prev = cur_node.right;
}
cur_prev = cur_node;
cur_node = cur_node.next;
}
dummy.next = null;
cur_head = next_head;
}
}
以为只要控制一下每一个level的head的寻找方式就行了; 虽然上面的代码其实是错的, 也就是实际上连题目给的这个tree都无法解决, 但是在调试的过程当中我发现了另外一个问题:
这个tree你怎么解决? 左边虽然触底了, 但是实际上中间还是有办法找到一个head, 或者更深的level的; 所以这题感觉用之前的那个方法根本没有办法做; 难怪tag里面提示DFS, 这题感觉就是要DFS来做; 而且要稍微利用一下DFS默认的order;
最后思考了一下, 好像还是找到办法了, 关键就是next_head每一个cur_head的循环的iteration里面, 一开始都要清空, 然后在走当前这个level的时候, 看到机会才能去更新next_head; 如果一次都没有更新成功, 那就是到了最后一层, 就结束; 最后还是AC了; 不过逻辑讲实话是写的有点复杂了, 自己调试, 超时了很久;
速度是2ms (30%), 还是可以接受的; 这个题目总体来说对于对循环的理解的基本功的要求可以算是很高了;
没有editorial;
Just share my iterative solution with O(1) space and O(n) Time complexity
public class Solution {
//based on level order traversal
public void connect(TreeLinkNode root) {
TreeLinkNode head = null; //head of the next level
TreeLinkNode prev = null; //the leading node on the next level
TreeLinkNode cur = root; //current node of current level
while (cur != null) {
while (cur != null) { //iterate on the current level
//left child
if (cur.left != null) {
if (prev != null) {
prev.next = cur.left;
} else {
head = cur.left;
}
prev = cur.left;
}
//right child
if (cur.right != null) {
if (prev != null) {
prev.next = cur.right;
} else {
head = cur.right;
}
prev = cur.right;
}
//move to next node
cur = cur.next;
}
//move to next level
cur = head;
head = null;
prev = null;
}
}
}
整体思路跟我的是类似的, 但是处理的比我的优雅的很多! 我当时苦于没有找到的, 把集中branch统一起来的写法, 他这里找到了; 诀窍就是, 不要把cur_node.left->cur_node.right的处理跟cur_node外面的加箭头处理区分开来; 说到底都是在一个level上面的traversal而已; 最后他的代码写的相当的对称和漂亮;
注意, 我们两的思路的一个核心都是, 要站在当前level, 然后找下一个level; 这个是这题重要的一个思考方式; 上一题很多人是站在当前level, 然后通过查询parent的child, 来改变当前level的traversal方式, 感觉这个思路就不是很适合这个第二题了;
I did some modification to increase its readability.
public class Solution {
public void connect(TreeLinkNode root) {
TreeLinkNode head=root;//The left most node in the lower level
TreeLinkNode prev=null;//The previous node in the lower level
TreeLinkNode curr=null;//The current node in the upper level
while (head!=null){
curr=head;
prev=null;
head=null;
while (curr!=null){
if (curr.left!=null){
if (prev!=null)
prev.next=curr.left;
else
head=curr.left;
prev=curr.left;
}
if (curr.right!=null){
if (prev!=null)
prev.next=curr.right;
else
head=curr.right;
prev=curr.right;
}
curr=curr.next;
}
}
}
}
所以到底改了什么? 完全就是一回事啊; 他这里其实就是想要在外围的循环用prev-cur而不是cur-next的模式; 但是实际上这题用cur-next的探脚模式更好理解的多;
My solution is similar, it’s basicly a level BFS without using additional qeue, as the next link already serves the queue functionality…
The difference of my solution is to introduce a dummy head node, which can save some if/else when dealling the first element in the list.
public class Solution {
public static void connect(TreeLinkNode root) {
TreeLinkNode nextHead = new TreeLinkNode(0);
nextHead.next = root;
while(nextHead.next != null){
TreeLinkNode tail = nextHead;
TreeLinkNode n = nextHead.next;
nextHead.next = null;
for(; n != null; n = n.next){
if(n.left != null){
tail.next = n.left;
tail = tail.next;
}
if(n.right != null){
tail.next = n.right;
tail = tail.next;
}
}
}
}
}
这个才是正儿八经的, 写的更加简练的一个做法, 他这里直接用这个nextHead来指向每一个level(实际上是下一个level)的开头, 每一个iteration开始的nextHead.next = null其实就是一个宣城: 我这个时候还不知道下一个level的head在哪里; 核心思路其实是差不多的, 不过这个是节省了很多对类似if not null这样的判断;
更简化的写法:
public void connect(TreeLinkNode root) {
if (root == null)
return;
TreeLinkNode dummy = new TreeLinkNode(0);
dummy.next = root;
while (dummy.next != null) {
TreeLinkNode cur = dummy.next, pre = dummy;
dummy.next = null;
while (cur != null) {
if (cur.left != null)
pre = pre.next = cur.left;
if (cur.right != null)
pre = pre.next = cur.right;
cur = cur.next;
}
}
}
void connect(TreeLinkNode *root) {
if (root == NULL) return;
TreeLinkNode * start = root;//start of cur level
TreeLinkNode * end = root;//end of all levels
TreeLinkNode * levelEnd = root;//cur level's end
while (start != NULL)
{
if (start->left != NULL)
{
end->next = start->left;
end = end->next;
}
if (start->right != NULL)
{
end->next = start->right;
end = end->next;
}
if (start == levelEnd)
{
start = start->next;//start points to next level
levelEnd->next = NULL;//set cur level's next to NULL
levelEnd = end;//set cur level's end as next level's end
}
else
{
start = start->next;
}
}
}
看起来有点奇怪的一个解法, 刚开始也确实是看不懂;
这个算法的写法是比较奇怪的, 不像大部分的写法那样, 有很强的level观念; 如果你实际上trace一遍就发现, 他这里更多的就是一个基本的BFS的traversal, 但是没有很强烈的level之间的分割的概念; 总体来说这个算法感觉设计相对难一些;
他这个代码当时理解的时候的一个难度在于, 他的命名和自己写的comment其实不准确, 他这里实际上算法的思路还是两个level同时traversal, start是在上层走, 然后end是在下层走, 并不是他这里自己描述的这两个定义; 当start走到le的时候, 基本确定e也已经把下一个level给走完了, 这个时候更新le就行了; 否则的话, 就是s和e的不断前进, 先前进s, 然后e根据s的child的情况来用跟其他写法类似的思路进行前进; 一个比较巧妙的技巧是用每一个level最后的le.next来完成一个缓存下一个level的head的操作;
The idea is simple: level-order traversal.
You can see the following code:
public class Solution {
public void connect(TreeLinkNode root) {
while(root != null){
TreeLinkNode tempChild = new TreeLinkNode(0);
TreeLinkNode currentChild = tempChild;
while(root!=null){
if(root.left != null) { currentChild.next = root.left; currentChild = currentChild.next;}
if(root.right != null) { currentChild.next = root.right; currentChild = currentChild.next;}
root = root.next;
}
root = tempChild.next;
}
}
}
大概画了一下trace:
实际上的操作跟之前的是差不多的; 就是用一个dummy来记录下一个level的head;
not necessary to create new node every level. you can create it at the beginning and keep reusing it.
这个意见其实就很trivial了;
Really simple solution. But it may not using constant space. Since you create a new node at every level, the space complexity should be O(log(n)).
Any way, I think it is the simplest solution. :)
If you program in C++, you may could free the new node after the inner while loop.
看来拿这个观点的人还不少; 那么直接把tc放在外面就行了, 很trivial的改动;
public void connect(TreeLinkNode root) {
TreeLinkNode dummyHead = new TreeLinkNode(0);
TreeLinkNode pre = dummyHead;
while (root != null) {
if (root.left != null) {
pre.next = root.left;
pre = pre.next;
}
if (root.right != null) {
pre.next = root.right;
pre = pre.next;
}
root = root.next;
if (root == null) {
pre = dummyHead;
root = dummyHead.next;
dummyHead.next = null;
}
}
}
LinkedList和TreeNode的题目, 还是得自己动手画一画; 尤其是这种需要指针操作的;
大概看看代码, 好像跟上面那个做法实际上是一样的;
The algorithm is a BFS or level order traversal. We go through the tree level by level. node is the pointer in the parent level, tail is the tail pointer in the child level.
The parent level can be view as a singly linked list or queue, which we can traversal easily with a pointer.
Connect the tail with every one of the possible nodes in child level, update it only if the connected node is not nil.
Do this one level by one level. The whole thing is quite straightforward.
Python
def connect(self, node):
tail = dummy = TreeLinkNode(0)
while node:
tail.next = node.left
if tail.next:
tail = tail.next
tail.next = node.right
if tail.next:
tail = tail.next
node = node.next
if not node:
tail = dummy
node = dummy.next
# 61 / 61 test cases passed.
# Status: Accepted
# Runtime: 100 ms
# 95.26%
意思是差不多的, 但是写法比较有趣;
这个是一个常规写法:
def connect(self, root):
while root:
cur = tmp = TreeLinkNode(0)
while root:
if root.left:
cur.next = root.left
cur = root.left
if root.right:
cur.next = root.right
cur = root.right
root = root.next
root = tmp.next
submission基本就是这么一回事了;
Problem Description
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
Difficulty:Medium
Total Accepted:122.7K
Total Submissions:361.7K
Contributor:LeetCode
Companies
facebookmicrosoftbloomberg
Related Topics
treedepth-first search
Similar Questions
Populating Next Right Pointers in Each Node