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

public class _116 {
    static class Solution1 {
        public Node connect(Node root) {
            dfs(root, null);
            return root;
        }

        public void dfs(Node node, Node parent) {
            if (node == null) return;
            if (parent != null) {
                if (node == parent.left) node.next = parent.right;
                else node.next = parent.next == null ? null : parent.next.left;
            }
            dfs(node.left, node);
            dfs(node.right, node);

        }
    }

    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);
            }
        }
    }

    static class Solution3 {
        public Node connect(Node root) {
            Node topLeft = root;
            //状态变化
            while (topLeft != null) {
                Node start = topLeft.left;
                int status = 0;//0,连接右节点，1，连接叔节点的左节点
                Node nextTopLeft = start;
                while (start != null && topLeft != null) {
                    if (status == 0) {
                        start.next = topLeft.right;
                        start = start.next;
                        topLeft = topLeft.next;
                    } else {
                        start.next = topLeft.left;
                        start = start.next;
                    }
                    status = (status + 1) % 2;
                }
                topLeft = nextTopLeft;
            }
            return root;

        }
    }
}