LeetCode 116. Populating Next Right Pointers in Each Node

思路

发现是一个树的遍历的题目，而且题目限制的比较死，是个满二叉树，这样处理的时候就避免了比较烦人的跨树指针的情况。比如下面这种建立4->5的指针：

    1
  2   3
4    5  6

第一时间想到的解法是弄个工作队列，然后一层一层遍历下去就行了，这个解法的空间复杂度是O(n)，不符合题目要求。后来再一想，其实既然上一层已经把下一层的next指针建立好了，就不用再从工作队列里去“回忆”了，只要在每一行的开头记住下一行在哪里就行，这样只要O(1)空间复杂度。
另外是如何设置next指针，一共有两个情况：

1. node自己的左孩子和右孩子连起来
2. node的右孩子与node右侧节点它的左孩子连起来

代码

O(n)空间复杂度方法

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        queue<TreeLinkNode*> workingQ;
        if(root == NULL)
            return;
        workingQ.push(root);
        while(!workingQ.empty())
        {
            TreeLinkNode* node = workingQ.front();
            workingQ.pop();
            if(node->left == NULL || node->right == NULL)
                continue;   //Leaf node
            node->left->next = node->right; //Inner connection
            if(node->next != NULL)
                node->right->next = node->next->left; //Outter connection
            workingQ.push(node->left);
            workingQ.push(node->right);
        }
    }
};

O(1)空间复杂度方法

class Solution {
public:
    void connect(TreeLinkNode *root) {
        TreeLinkNode* nextRowPtr = root;
        TreeLinkNode* node = root;
        bool atRowStart = true;
        while(nextRowPtr != NULL)
        {
            if(node->left == NULL || node->right == NULL)
                break;   //Leaf node
            if(atRowStart)
            {
                atRowStart = false;
                nextRowPtr = node->left;
            }
            node->left->next = node->right; //Inner connection
            if(node->next != NULL)
            {
                node->right->next = node->next->left; //Outter connection
                node = node->next;
            }
            else
            {
                node = nextRowPtr;
                atRowStart = true;  //End of current row
            }
        }
    }
};