LeetCode –Populating Next Right Pointers in Each Node II

题目：

Given a binary tree

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *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.

Follow up:

• You may only use constant extra space.
• Recursive approach is fine, you may assume implicit stack space does not count as extra space for this problem.

Example 1:

Input:

 root = [1,2,3,4,5,null,7]

Output:

 [1,#,2,3,#,4,5,7,#]

Explanation:

Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

Constraints:

• The number of nodes in the given tree is less than 6000.
• -100 <= node.val <= 100

实现

      由于不是完全二叉树， 在寻找其next节点时，与其父节点同层的相邻的节点可能不存在， 需要特殊处理。 

• 递归方式，  当前节点获取next时， 由于会出现其父节点相邻节点的左右子树为空的情况，需要先处理右子树， 如果不先处理右子树，会导致左节点无法找到next节点提前退出。 

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/


/* recursive
class Solution {
public:
    Node* connect(Node* root) {
        if (root == NULL) {
            return NULL;
        }
        if (root->left) {
            root->left->next = root->right ? root->right : nextNode(root->next);
        }
        if (root->right) {
            root->right->next = nextNode(root->next) ;
        }
        
        //connect(root->left);  寻找当前节点字节点next时， 会出现其next节点左右子节点为空的情况， 如果不先处理右节点，导致其子节点无法找到next节点
        connect(root->right);   
        connect(root->left)
        return root;
    }
    
    Node* nextNode(Node* root){
        if (root == NULL) {
            return NULL;
        }
        if (root->left) {
            return root->left;
        }
        else if (root->right) {
            return root->right;
        }
        else {
            return nextNode(root->next);
        }

    }
};

• 非递归方式： prehead 记录每层的第一个节点， 通过游标cur遍历当前层，使用prehead->next节点继续处理下一层

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

/* no Recursive  */
class Solution {
public:
    Node* connect(Node* root) {
      Node* prehead = new  Node(0, NULL, NULL, NULL);
      Node* cur = prehead;
      Node* head = root;
      
      while (head) {
          
          if (head->left) {
              cur->next = head->left;
              cur = cur->next;
          }
          if (head->right){
              cur->next = head->right;
              cur = cur->next;
          }
          
          head = head->next;
          // new level head node
          if (!head) {
              cur = prehead;
              head = prehead->next;
              prehead->next = NULL;
          }
      }
      
      delete prehead;
      return root;
    }
};