本文共 3310 字，大约阅读时间需要 11 分钟。

������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������

������������

������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������ O(n)���������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������

���������������

���������������

public class lc117 {
    Node next = null, nextStart = null; // used to store next node in level and starting nodes of next level
    public Node connect(Node root) {
        if (root == null) return null;
        Node start = root;
        while (start != null) {
            next = null;
            nextStart = null;
            for (Node p = start; p != null; p = p.next) {
                // Process left child
                if (p.left != null) {
                    if (next == null) {
                        nextStart = connectOne(p.left);
                    } else {
                        next.next = p.left;
                    }
                }
                // Process right child
                if (p.right != null) {
                    connectOne(p.right);
                }
            }
            start = nextStart;
        }
        return root;
    }
    public void connectOne(Node node) {
        if (next == null) {
            next = node;
            nextStart = node;
        } else {
            next.next = node;
        }
    }
}

���������������

��������������������������������������������������������������������������������������������������������������������������������������������������������������������������� O(n) ��������������������������������������� O(1)���������������������������������������