[leetcode] Populating Next Right Pointers in Each Node II


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,

         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL
Show Tags
Show Similar Problems

 

It’s similar to the former problem Populating Next Right Pointers in Each Node I. The key to this question is to implement two functions: findNextLevelStartNode and findNextLevelNextNode

 

/**
 * 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) {
        TreeLinkNode * p, * startNode;
        TreeLinkNode * q;
        while((startNode = findNextLevelStartNode(root)) != NULL){
             p = startNode;
             while((q = findNextLevelNextNode(root, p)) != NULL ){
                    p->next = q;
                    p = q;
             }
             root = startNode;
        }
    } 
    //find the leftmost node in next level
    //if return NULL, traversal is end
    TreeLinkNode * findNextLevelStartNode(TreeLinkNode * root){
        if(root == NULL){
            return NULL;
        }
        if(root->left != NULL) return root->left;
        if(root->right != NULL) return root->right;
        return findNextLevelStartNode(root->next);
    }
    //find next node
    //if return NULL, current level is end
    TreeLinkNode * findNextLevelNextNode(TreeLinkNode *& root, TreeLinkNode * node){
        if(root == NULL){
            return NULL;
        }
        if(node == NULL){
            if(root->left != NULL) return root->left;
            if(root->right != NULL) return root->right;
            root = root->next;
            return findNextLevelNextNode(root, node);
        }
        if(node == root->left){
            if(root->right != NULL) return root->right;
            else{
                root = root->next;
                return findNextLevelNextNode(root, node);
            }
        }
        if(node == root->right){
            root = root->next;
            return findNextLevelNextNode(root, node);
        }
        if(root->left != NULL) return root->left;
        if(root->right != NULL) return root->right;
        root = root->next;
        return findNextLevelNextNode(root, node);
    }
};

Untitled

 

Leave a comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.