Populating Next 오른쪽 포인터 각 노드 II 임의의 (완벽 하지 않 음) 이 진 트 리 에 next 포인터 추가 @ LeetCode

http://blog.csdn.net/fightforyourdream/article/details/14514165
위의 문 제 를 바탕 으로 확장 합 니 다. 이때 수 는 완벽 한 이 진 트 리 가 아니 라 임의의 이 진 트 리 입 니 다.
이 문 제 는 좀 까다 로 우 니, 시간 이 있 으 면 나중에 다시 연구 해 보 자.

package Level4;

import Utility.TreeLinkNode;

/**
 * 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
Discuss


 *
 */
public class S117 {

	public static void main(String[] args) {

	}

	public static void connect(TreeLinkNode root) {
		//         
		if (root == null){
			return;
		}
		
		//    root    next node
		TreeLinkNode rootNext = root.next;
		TreeLinkNode next = null;		//          
		
		// rootNext   null             node
		// next   null                    
		while (rootNext != null && next == null)
		{
			if (rootNext.left != null){	//      
				next = rootNext.left;
			} else{
				next = rootNext.right;
			}
			rootNext = rootNext.next;
		}
 
		if (root.left != null)
		{
			if (root.right != null){	//	    
				root.left.next = root.right;
			}else{						//     
				root.left.next = next;
			}
		}
		if (root.right != null){		//     
			root.right.next = next;
		}
		
		connect(root.right);		//           
		connect(root.left);
    }
}

두 번 째 로 한 곳 의 bug 를 수정 하 였 습 니 다.
역시 LeetCode 를 만 드 는 진 리 는: 만 나 서 모 르 는 것 = > 답 찾기 = > 스스로 이해 해서 쓰 거나 외 우 는 것 = > 시간 이 지나 면 두 번 째 로 다시 하 는 것 이다.
예 를 들 어 이 문제 에서 제 가 가장 기억 에 남 는 것 은 오른쪽 나 무 를 먼저 처리 한 다음 에 왼쪽 나 무 를 처리 해 야 한 다 는 것 입 니 다. 이 점 을 알 면 충분히 쓸 수 있 습 니 다.
관건 은 next 노드 가 어디 에 있 는 지 찾 는 것 이 고 rootnext 노드 가 어디 에 있 는 지 찾 아야 합 니 다.그 while 순환 이 문제 풀이 의 관건 이다.

/**
 * 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 rootnext = root.next;
        TreeLinkNode next = null;
        while(rootnext != null){
            if(rootnext.left != null){
                next = rootnext.left;
                break;
            }else if(rootnext.right != null){
                next = rootnext.right;
                break;
            }else{
                rootnext = rootnext.next;
            }
        }
        
        if(root.right != null){
            root.right.next = next;
        }
        if(root.left != null){
            if(root.right != null){
                root.left.next = root.right;
            }else{
                root.left.next = next;
            }
        }
        
        connect(root.right);
        connect(root.left);
    }
}