Populating Next Right Pointers in Each Node [LeetCode]

4199 단어 LeetCode
Given a binary tree
    struct TreeLinkNode {

      TreeLinkNode *left;

      TreeLinkNode *right;

      TreeLinkNode *next;

    }


 
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to  NULL .
Initially, all next pointers are set to  NULL .
Note:
  • You may only use constant extra space.
  • You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

  •  
    For example,Given the following perfect binary tree,
             1
    
           /  \
    
          2    3
    
         / \  / \
    
        4  5  6  7
    
    

     
    After calling your function, the tree should look like:
             1 -> NULL
    
           /  \
    
          2 -> 3 -> NULL
    
         / \  / \
    
        4->5->6->7 -> NULL
    
    

     
     Summary: The simplest way is BFS, but we need non-constant extra space. So, I traverses the tree Pre-order, and uses one node pointer for every level. 
     1     void traverse(TreeLinkNode *root, int depth, vector<TreeLinkNode *> &current) {
    
     2         if(root->left != NULL && root->right != NULL){
    
     3             if(current.size() < depth + 1)
    
     4                 current.push_back(root->right);
    
     5             else{
    
     6                 current[depth]->next = root->left;
    
     7                 current[depth] = root->right;
    
     8             }
    
     9             root->left->next = root->right; 
    
    10             //traverse the left subtree
    
    11             traverse(root->left, depth + 1, current);
    
    12             //traverse the right subtree
    
    13             traverse(root->right, depth + 1, current);
    
    14         }
    
    15     }
    
    16     
    
    17     void connect(TreeLinkNode *root) {
    
    18         if(root == NULL)
    
    19             return;
    
    20         
    
    21         vector<TreeLinkNode *> current;
    
    22         traverse(root, 0, current);
    
    23     }

    좋은 웹페이지 즐겨찾기