LeetCode: Populating Next Right Pointer 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

next_로head와 last_다음 처리해야 할 루트 노드와 마지막으로 처리한 가장 오른쪽 노드를 기록합니다.알고리즘은 간단하지만 코드는 복잡하다.

/**
 * 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) {
		// Start typing your Java solution below
		// DO NOT write main() function
		TreeLinkNode cur_head = root;
		while(cur_head != null){
			TreeLinkNode cur = cur_head;
			TreeLinkNode next_head = null;
			TreeLinkNode last_node = null;
			while(cur != null){
				if(cur.left == null && cur.right == null);
				else if(cur.left != null && cur.right != null){
					if(last_node != null)
						last_node.next = cur.left;
					cur.left.next = cur.right;
					last_node = cur.right;
					if(next_head == null)
						next_head = cur.left;
				}
				else{
					TreeLinkNode child = null;
					if(cur.left != null)
						child = cur.left;
					else
						child = cur.right;
					if(last_node != null)
						last_node.next = child;
					last_node = child;
					if(next_head == null)
						next_head = child;
				}
				cur = cur.next;
			}
			if(last_node != null)
				last_node.next = null;
			cur_head = next_head;
		}
	}
}

귀속 해법은 p로 이 지향하는next 노드를 가리키며 층층이 오른쪽에서 왼쪽으로 옮겨간다.넥스트를 피했습니다_헤드 처리.

/**
 * 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) {
		// Start typing your Java solution below
		// DO NOT write main() function
		if (root == null) {
			return;
		}
		TreeLinkNode cur = root.next;
		TreeLinkNode p = null;
		while (cur != null) { // find last right node (left or right)
			if (cur.left != null) {
				p = cur.left;
				break;
			}
			if (cur.right != null) {
				p = cur.right;
				break;
			}
			cur = cur.next;
		}
		if (root.right != null) 
			root.right.next = p;
		if (root.left != null)
			root.left.next = root.right != null ? root.right : p;
		connect(root.right); // from right to left
		connect(root.left);
	}
}

왼쪽에서 오른쪽으로 쓸 수도 있어요.다음 왼쪽 오른쪽 코드는judgelarge를 통과할 수 없습니다. 각 층의 노드 (root.left) 가 반복적으로 작동하기 때문에, 각 층의 가장 왼쪽 뿌리를 저장할 양을 설정해야 합니다.

/**
 * 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) {
		// Start typing your Java solution below
		// DO NOT write main() function
		if (root == null)
			return;
		TreeLinkNode cur = root.next;
		TreeLinkNode p = null;
		while (cur != null) { // find last right node (left or right)
			if (cur.left != null) {
				p = cur.left;
				break;
			}
			if (cur.right != null) {
				p = cur.right;
				break;
			}
			cur = cur.next;
		}
		if (root.left != null)
			root.left.next = root.right != null ? root.right : p;
		if (root.right != null) 
			root.right.next = p;
    	if(cur != null)
			connect(cur);
		connect(root.left);
	}
}