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
1 public class Solution { 2 public void connect(TreeLinkNode root) { 3 TreeLinkNode head=null; 4 TreeLinkNode prev =null; 5 TreeLinkNode cur = root; 6 7 while(cur!=null){ 8 //针对每一层，利用Prev进行next连接 9 while(cur!=null){ 10 11 if(cur.left!=null){ 12 if(prev==null)//prev空，说明cur.left是下一层的头节点。 13 head = cur.left; 14 else//不为空，正常连接next指针， 15 prev.next =cur.left; 16 prev = cur.left; //移动prev 17 } 18 19 if(cur.right!=null){ 20 if(prev==null)//prev空，说明cur.right是下一层的头节点。 21 head = cur.right; 22 else //不为空，正常连接next指针， 23 prev.next=cur.right; 24 prev = cur.right; 25 } 26 27 cur = cur.next; 28 } 29 //此层结束，准备进入下一层。 30 cur = head; 31 head = null; 32 prev = null; 33 } 34 } 35 }