I think BFS is much suitable for both this question and the Populating Next Right pointers in Each Node


  • 0
    Y
    class Solution {
    public:
        void connect(TreeLinkNode *root) {
            if (root == NULL) return;
            queue<TreeLinkNode*> q;
            q.push(root);
            while (!q.empty()) {
                int layerSize = q.size();
                for (int i = 0; i < layerSize; i++) {
                    TreeLinkNode *curr = q.front();
                    q.pop();
                    if (curr->left) q.push(curr->left);
                    if (curr->right) q.push(curr->right);
                    if (i == layerSize - 1) {
                        curr->next = NULL;
                    } else {
                        curr->next = q.front();
                    }
                }
            }
        }
    };

  • 0

    BFS uses extra space, the problem itself mentions the requirement explicitly to use only constant space.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.