LeetCode "Populating Next Right Pointers in Each Node"

Apparently BFS is the most obvious one.. but it is not that simple - only constant extra space is provided.

Then the only strategy to take is recursion. I bogged down for quite while.. only after checked http://leetcode.com/2010/03/first-on-site-technical-interview.html, I got enlightment: pick a pen and a piece of paper, and simulate the procedure by drawing - this strategy is working so well on diagram-like problems! Just like "starting from enumeration and check pattern" strategy, a good solution starts from basics.

class Solution {
public:
    void connect(TreeLinkNode *p) {
        if (!p) return;
        if (p->left)    p->left->next = p->right;    // with the same parent
        if (p->right)    p->right->next = (p->next) ? p->next->left : NULL;
        connect(p->left);
        connect(p->right);
    }
};

LeetCode "Populating Next Right Pointers in Each Node",布布扣,bubuko.com

LeetCode "Populating Next Right Pointers in Each Node"

原文：http://www.cnblogs.com/tonix/p/3857655.html