Monday, March 10, 2014

Populating Next Right Pointers in Each Node II (Java and Python)

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?
  • You may only use constant extra space.
For example,
Given the following binary tree,
       /  \
      2    3
     / \    \
    4   5    7
After calling your function, the tree should look like:
         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL
Solution : The main idea actually is tree level traversal, we can just use one node called current represent current level (start from root) and two other nodes which called nextLevelHead and nextLevelEnd to record next level's left child and right child and when current node is null then exchange current and nextLevelHead until nextLevelHead is also null