116.md

#116. Populating Next Right Pointers in Each Node 题目链接

public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null) {
            return;
        }
        // 利用队列的性质，采用广度优先便利
        LinkedList<TreeLinkNode> ll = new LinkedList<>();
        ll.add(root);
        // 以层为单位进行循环
        while (ll.size() != 0) {
            int n = ll.size();
            TreeLinkNode node = ll.pop();
            // 层内循环
            for (int i = 0; i < n; i++) {
                if (node.left != null) {
                    ll.addLast(node.left);
                    ll.addLast(node.right);
                }
                // 如果是层的最后一个，next设为null
                if (i < n - 1) {
                    TreeLinkNode nextNode = ll.pop();
                    node.next = nextNode;
                    node = nextNode;
                } else {
                    node.next = null;
                }
            }
        }
    }
}

空间复杂度为常数的方法

public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null) {
            return;
        }
        // 额外设置两个变量，其中pre指向每一层第一个结点，cur用来遍历这一层所有结点
        TreeLinkNode pre = root;
        TreeLinkNode cur;
        while (pre.left != null) {
            cur = pre;
            while (cur != null) {
                // 分为两种情况，左子树的next直接指向右子树，右子树的next指向右边结点的左子树
                cur.left.next = cur.right;
                if (cur.next != null) {
                    cur.right.next = cur.next.left;
                }
                cur = cur.next;
            }
            pre = pre.left;
        }
    }
}