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,
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:
/** * 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) { TreeLinkNode firstNodeLevel = root; TreeLinkNode firstNodeNextLevel = null; while(firstNodeLevel != null) { TreeLinkNode pointer = firstNodeLevel; TreeLinkNode nextLevelTemp = null; while(pointer!=null) { if(pointer.left!=null) { if(firstNodeNextLevel == null) firstNodeNextLevel = pointer.left; else nextLevelTemp.next = pointer.left; nextLevelTemp = pointer.left; } if(pointer.right!=null) { if(firstNodeNextLevel == null) firstNodeNextLevel = pointer.right; else nextLevelTemp.next = pointer.right; nextLevelTemp = pointer.right; } pointer = pointer.next; } firstNodeLevel = firstNodeNextLevel; firstNodeNextLevel = null; } } }
No comments :
Post a Comment