import java.util.ArrayList;
import java.util.List;

public class _117 {
    static class Solution1 {
        public Node connect(Node root) {
            //换成了二叉树,逻辑发生变化
            //强制连接右节点，parent，or uncle 无可用，parent = parent.next || uncle = uncle.next;
            Node tl = root;
            while (tl != null) {
                //这里，寻找第一个可用的左侧节点
                Node s = null;
                while (tl != null && s == null) {
                    if (tl.left == null && tl.right == null) tl = tl.next;
                    else {
                        s = tl.left == null ? tl.right : tl.left;
                        break;
                    }
                }
                Node nextTl = s;
                //从s开始不断连接
                while (tl != null && s != null) {
                    if (tl.left == null && tl.right == null) {
                        tl = tl.next;
                        continue;
                    }
                    if (s == tl.left) {
                        if (tl.right != null) {
                            s.next = tl.right;
                            s = s.next;
                        }
                        tl = tl.next;
                    } else if (s == tl.right) {
                        tl = tl.next;
                    } else {
                        s.next = tl.left == null ? tl.right : tl.left;
                        s = s.next;
                    }
                }
                tl = nextTl;
            }
            return root;
        }
    }

    static class Solution2 {
        public Node connect(Node root) {
            //bfs
            List<Node> cur = new ArrayList<>();
            if (root != null) cur.add(root);
            while (cur.size() > 0) {
                handleSameLevel(cur);
                List<Node> next = new ArrayList<>();
                for (Node item : cur) {
                    if (item.left != null) next.add(item.left);
                    if (item.right != null) next.add(item.right);
                }
                cur = next;
            }
            return root;

        }

        public void handleSameLevel(List<Node> lv) {
            for (int i = 0; i < lv.size() - 1; i++) {
                lv.get(i).next = lv.get(i + 1);
            }
        }
    }
}