116. 填充每个节点的下一个右侧节点指针(116. Populate the next right node pointer for each node)

给定一个 完美二叉树 ,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。

初始状态下,所有 next 指针都被设置为 NULL。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

模拟队列

class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return null;
        }
        Node cur = root, tail = root;
        int size = 1;
        while (cur != null) {
            Node pre = null;
            for (int i = 1; i <= size; ++i) {
                if (cur.left != null) {
                    tail.next = cur.left;
                    tail = cur.left;
                }
                if (cur.right != null) {
                    tail.next = cur.right;
                    tail = cur.right;
                }
                if (pre != null) {
                    pre.next = cur;
                }
                pre = cur;
                cur = cur.next;
            }
            pre.next = null;
            size <<= 1;
        }
        return root;
    }
}

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {
    }

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
}

官方的题解

class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return root;
        }

        // 从根节点开始
        Node leftmost = root;

        while (leftmost.left != null) {

            // 遍历这一层节点组织成的链表,为下一层的节点更新 next 指针
            Node head = leftmost;

            while (head != null) {

                // CONNECTION 1
                head.left.next = head.right;

                // CONNECTION 2
                if (head.next != null) {
                    head.right.next = head.next.left;
                }

                // 指针向后移动
                head = head.next;
            }

            // 去下一层的最左的节点
            leftmost = leftmost.left;
        }

        return root;
    }
}

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {
    }

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
}
————————

Given a} perfect binary tree, all leaf nodes are in the same layer, and each parent node has two child nodes. Binary tree is defined as follows:

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
Fill in each of its next pointers so that this pointer points to its next right node. If the next right node cannot be found, set the next pointer to null.

In the initial state, all} next pointers are set to null.

Source: leetcode
Link: https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.

Simulated queue

class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return null;
        }
        Node cur = root, tail = root;
        int size = 1;
        while (cur != null) {
            Node pre = null;
            for (int i = 1; i <= size; ++i) {
                if (cur.left != null) {
                    tail.next = cur.left;
                    tail = cur.left;
                }
                if (cur.right != null) {
                    tail.next = cur.right;
                    tail = cur.right;
                }
                if (pre != null) {
                    pre.next = cur;
                }
                pre = cur;
                cur = cur.next;
            }
            pre.next = null;
            size <<= 1;
        }
        return root;
    }
}

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {
    }

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
}

Official explanation

class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return root;
        }

        // 从根节点开始
        Node leftmost = root;

        while (leftmost.left != null) {

            // 遍历这一层节点组织成的链表,为下一层的节点更新 next 指针
            Node head = leftmost;

            while (head != null) {

                // CONNECTION 1
                head.left.next = head.right;

                // CONNECTION 2
                if (head.next != null) {
                    head.right.next = head.next.left;
                }

                // 指针向后移动
                head = head.next;
            }

            // 去下一层的最左的节点
            leftmost = leftmost.left;
        }

        return root;
    }
}

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {
    }

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
}