117. Populating Next Right Pointers in Each Node II

제목:
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

 
 
Hide Tags
 
Tree   Depth-first Search
 
링크:http://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/
문제:
마찬가지로 DFS입니다.다음 문제와 달리 주어진 입력은 완전한 두 갈래 나무가 아니기 때문에 합리적인 넥스트 값이 존재하는지 판단하기 위해 조건을 넣어야 한다.또한 왼쪽 노드와 오른쪽 노드의 유효성도 검증해야 한다.마지막으로 오른쪽 노드를 연결한 다음에 왼쪽 노드를 연결합니다.
Time Complexity - O(n), Space Complexity - O(1).

public class Solution {

    public void connect(TreeLinkNode root) {

        if(root == null)

            return;

        TreeLinkNode node = root.next;

        while(node != null){

            if(node.left != null){

                node = node.left;

                break;

            } else if(node.right != null){

                node = node.right;

                break;

            } 

            node = node.next;

        }

        

        if(root.right != null){

            root.right.next = node;

            if(root.left != null)

                root.left.next = root.right;

        } else {

            if(root.left != null)

                root.left.next = node;

        }

        

        connect(root.right);

        connect(root.left);

    }

}

 
테스트:
Reference:
http://www.cnblogs.com/springfor/p/3889327.html