Populating Next Right Pointers in Each Node 系列

题目的意思是使用 next 指针连接树中同一层次的节点，主要的难点在于空间复杂度必须在常数级

题型一

高度差为 0 的完美满二叉树特点：每一个节点都有一个相邻接点，比如有左节点，那么它的下一个就是右节点，有右节点那么它的下一个可以是空或者是父节点的下一个节点的左节点

Node* connect(Node* root) {
    if (root == NULL) return root;
    Node *pre=root;
    Node *cur=NULL;

    while(pre->left) {
        cur = pre;
        while(cur) {
            cur->left->next = cur->right;
            if (cur->next) cur->right->next = cur->next->left;
            cur=cur->next;
        }
        pre = pre->left;
    }
    return root;
}

题型二

给定任意形状的二叉树，高度可以不一，只不过需要多几步判断边界

Node* connect(Node* root) {
    if (root == NULL) return root;
    Node* pre = root;
    Node* cur;
    pre->next = NULL;
    while(pre!=NULL) {
        cur = pre;
        while(cur != NULL) {
            if (cur->left) {
                if (cur->right)
                    cur->left->next = cur->right;
                else
                    cur->left->next = getNext(cur);
            }

            if (cur->right) {
                cur->right->next = getNext(cur);
            }
            cur = cur->next;        
        }
        if (pre->left)
            pre = pre->left;
        else if (pre->right)
            pre = pre->right;
        else
            pre = getNext(pre);
    }
    return root;
}

// 不停地往上层级的平行节点找，优先返回左节点然后是右节点，找不到返回空
Node* getNext(Node* node) {
    node = node->next;

    while(node!=NULL) {
        if (node->left)
            return node->left;
        else if (node->right)
            return node->right;
        node = node->next;
    }
    return NULL;
}

#tree

LRU cache Power of 系列