116/117-填充右侧指针

LeetCode 116. Populating Next Right Pointers in Each Node

LeetCode-116

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.

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.

method 1: 层序遍历

当前节点弹出后，队列里的头结点就是同一层的下一个节点
每一层的最后一个节点不需要处理next指针

Node* connect(Node* root) {
    if (!root) return root;
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            Node *cur = q.front();
            q.pop();
            if (i < size - 1) cur->next = q.front();    // 非最后一个节点
            if (cur->left) q.push(cur->left);
            if (cur->right) q.push(cur->right);
        }
    }
    return root;
}

时间复杂度：$O(n)$，每个节点都会入队一次
空间复杂度：$O(n)$，完美二叉树最后一层有$N/2$个节点，BFS的空间复杂度取决于一个层级上的最大元素数量，也就是最多会有多少个节点在队列里

method 2: 利用next指针

• 对于有相同父节点的两个相邻节点，可以直接head->left->next=head->right
• 对于不同父节点的两个相邻节点，可以通过第一个节点的父节点的next指针找到第二个节点的父节点，所以就是head->right->next=head->next->left

Node* connect(Node* root) {
    if (!root) return root;
    Node *leftNode = root;
    while (leftNode->left) {    // 每次都从最左边开始
        Node *head = leftNode;
        while (head) {
            head->left->next = head->right;
            if (head->next) {
                head->right->next = head->next->left;
            }
            head = head->next;
        }
        leftNode = leftNode->left;
    }
    return root;
}

时间复杂度：$O(n)$，每个节点都会遍历一次
空间复杂度：$O(1)$

---

LeetCode 117. Populating Next Right Pointers in Each Node II

LeetCode-117

Given a binary tree(不是完美二叉树)

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.

Example 1:

Input: root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]

method

跟116代码完全一样，区别在于不是完美二叉树，但还是可以用层序遍历解决

Node* connect(Node* root) {
    if (!root) return root;
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            Node *cur = q.front();
            q.pop();
            if (i < size - 1) cur->next = q.front();    // 非最后一个节点
            if (cur->left) q.push(cur->left);
            if (cur->right) q.push(cur->right);
        }
    }
    return root;
}