5.1.10 Populating Next Right Pointers in Each Node II

1889 단어
Notes:
 
Follow up for problem "Populating Next Right Pointers in Each Node".
 
What if the given tree could be any binary tree? Would your previous solution still work?
 
Note:
 
You may only use constant extra space.
 
For example,
 
Given the following binary tree,
 

 
/\
 
2 3
 
/\\
 
4 5 7
 
After calling your function, the tree should look like:
 
1 -> NULL
 
/\
 
2 -> 3 -> NULL
 
/\\
 
4-> 5 -> 7 -> NULL
 
 
Solution: 1. iterative way with CONSTANT extra space.
 
2. iterative way + queue. Contributed by SUN Mian(손관).
 
3. recursive solution.
 
*/
 
 
 
/**
 
* 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) {}
 
* };
 
*/
void connect_2(TreeLinkNode *root) {
        if (root == NULL) return;
        queue<TreeLinkNode *> q;
        q.push(root);
        q.push(NULL);
        TreeLinkNode *last = NULL;
        TreeLinkNode dummy(-1);
        TreeLinkNode *pre = &dummy;
        while (!q.empty()) {
            TreeLinkNode *node = q.front();
            q.pop();
            if (node == NULL) {
                if (dummy.next) q.push(NULL);
                pre = &dummy;
                pre->next = NULL;
            } else {
                pre->next = node;
                pre = pre->next;
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
    }

좋은 웹페이지 즐겨찾기