正文
leetcode 117 Populating Next Right Pointers in Each Node II ----- java
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
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
这道题和上一道题的区别在于，上一道的树是满二叉树，这一个并不是。
还是先使用队列做了一次，ac但是速度并不是很快。
/**
* 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 ; Queue queue = new LinkedList<TreeLinkNode>(); queue.add(root); while( !queue.isEmpty() ){ int size = queue.size();
TreeLinkNode node1 = (TreeLinkNode) queue.poll();
if( node1.left != null )
queue.add(node1.left);
if( node1.right != null)
queue.add(node1.right);
if( size == 1)
continue;
TreeLinkNode node2 = (TreeLinkNode) queue.poll();
if( node2.left != null )
queue.add(node2.left);
if( node2.right != null)
queue.add(node2.right);
for( int i = 2;i<size;i++){
node1.next = node2;
node1 = node2;
node2 = ( TreeLinkNode ) queue.poll();
if( node2.left != null )
queue.add(node2.left);
if( node2.right != null)
queue.add(node2.right);
}
node1.next = node2;
} }
}
但是题目中要求是常数空间。
所以还需要修改。
记录上一行的开始和下一行的开始，然后依次改变next。
/**
* 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 low = null ;//指的是下面一行的第一个结点
TreeLinkNode up = root;
if( root.left != null )
low = root.left;
else if( root.right != null )
low = root.right;
while( low != null ){
TreeLinkNode start = low;
TreeLinkNode upStart = up;
helper(start,upStart);
while( low != null ){
if( low.left != null ){
TreeLinkNode node = low.left;
up = low;
low = node;
break;
}
if( low.right != null ){
TreeLinkNode node = low.right;
up = low;
low = node;
break;
}
low = low.next;
} }
} public void helper(TreeLinkNode start,TreeLinkNode upStart){ if( upStart.left != null){
if( upStart.right != null){
start.next = upStart.right;
start = start.next;
}
}
upStart = upStart.next;
while( upStart != null ){ if( upStart.left != null ){
start.next = upStart.left;
start = start.next;
if( upStart.right != null ){
start.next = upStart.right;
start = start.next;
}
}else if( upStart.right != null ){
start.next = upStart.right;
start = start.next;
}
upStart = upStart.next;
}
}
}
