Populating Next Right Pointers in Each Node

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

Given a binary tree

struct TreeLinkNode {

  TreeLinkNode \*left;

  TreeLinkNode \*right;

  TreeLinkNode \*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.

Note:

You may only use constant extra space.

You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

Thoughts

对完美二叉树每个结点增加next指针指向每层下一个结点。不难想到按层遍历，对每个结点，假设它所在的层已经连好了，通过它去连接下一层的结点。利用完美二叉树的性质，让cur->right去连接cur->next->left实现跨子树连接。当前结点处理好后，直接利用它的next就蹦到本层下一个结点。当next为null时说明本层已经遍历完，下层都已连好，需要一个额外指针next_lev记录下层第一个结点。

Code

/*
 * @lc app=leetcode id=116 lang=cpp
 *
 * [116] Populating Next Right Pointers in Each Node
 */

// @lc code=start
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() {}

    Node(int _val, Node* _left, Node* _right, Node* _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/
class Solution {
public:
    Node* connect(Node* root) {
        Node *cur = root, *next_lev = cur;
        while (cur != nullptr && cur->left != nullptr) {
            if (next_lev == cur) {
                next_lev = cur->left;
            }
            cur->left->next = cur->right;
            if (cur->next == nullptr) {
                cur = next_lev;
            } else {
                cur->right->next = cur->next->left;
                cur = cur->next;
            }
        }
        return root;
    }
};
// @lc code=end

Analysis

Errors:

1. 初始化TreeLinkNode nextLevel = null错误; 导致只执行了第一层

时间复杂度O(n), 空间复杂度O(1).