116.Populating Next Right Pointers in Each Node

Tags: Tree Depth-first Search Medium

Links: https://leetcode.com/problems/populating-next-right-pointers-in-each-node/

---

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Follow up:

• You may only use constant extra space.
• Recursive approach is fine, you may assume implicit stack space does not count as extra space for this problem.

Example 1:

Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

Constraints:

• The number of nodes in the given tree is less than 4096.
• -1000 <= node.val <= 1000

---

层序遍历的变形的非递归写法。

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    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) return nullptr;

        queue<Node *> q; //level traversal方法
        q.push(root);
        while (!q.empty()) {
            int n = q.size(); //n来记录每一层的节点数
            Node * p = q.front();
            q.pop();
            bool flag = false;
            //p始终是每行的第一个节点，后面用来记录上一个节点
            if (p -> left && p -> right) {
                q.push(p -> left);
                q.push(p -> right);
                flag = true; //如果为true，后面的节点只需要判断一次
            }

            if (n == 1) p -> next = nullptr;
            else {
                for (int i = 0; i < n - 1; ++i) {
                    Node * tmp = q.front();
                    q.pop();
                    if (flag) {
                        q.push(tmp -> left);
                        q.push(tmp -> right);
                    }
                    p -> next = tmp;
                    p = tmp;
                }
                p -> next = nullptr;
            }
        }

        return root;
    }
};

递归写法形式就比较简单了：

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    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) return nullptr;

        //如果root -> left非空，那么root -> right必非空
        if (root -> left) {
            root -> left -> next = root -> right;
            if (root -> next) root -> right -> next = root -> next -> left;
            else root -> right -> next = nullptr;
            connect(root -> left);
            connect(root -> right);
        }

        return root;
    }
};

方法是判断当前节点的左子节点是否为空，不为空则可以直接确定左节点的next指针指向，右子节点略微复杂，它的next指针指向由当前节点决定，如果当前节点的next指针为空，则右节点的next指针也为空，否则直接指向当前节点的next指针指向节点的左子节点。

更简洁的写法是利用一个指针start记录每一层的起始节点（其实和利用辅助队列的方法是类似的），利用另一个指针cur去遍历当前层，然后建立下一层的连接，利用start的left作为探测，其实相当于模拟了队列。

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    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) return nullptr;

        Node *start = root, *cur = nullptr;
        while (start -> left) {
            cur = start;
            while (cur) {
                cur -> left -> next = cur -> right;
                if (cur -> next) cur -> right -> next = cur -> next -> left;
                cur  = cur -> next;
            }
            start = start -> left;
        }

        return root;
    }
};