跟进问题“在每个节点中填充下一个正确的指针”。层次遍历二叉树

本题源自leetcode

------------------------------------------------------------

例如:

         1
       /  \
      2    3
     / \    \
    4   5    7

结果：

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL

思路1：

按层遍历 ：每次弹出当前层的所有节点

struct TreeLinkNode {
   int val;
  TreeLinkNode *left, *right, *next;
   TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
  };

 void connect(TreeLinkNode *root) {
        if(root==NULL)
            return;
        queue<TreeLinkNode*> que;
        que.push(root);
        while(!que.empty()){
            TreeLinkNode* currentNode=que.front();
            que.pop();
            int currentLen=que.size();
            if(currentNode->left)
                que.push(currentNode->left);
            if(currentNode->right)
                que.push(currentNode->right);
            for(int i=0;i<currentLen;i++){
                TreeLinkNode* nextNode=que.front();
                que.pop();
                currentNode->next=nextNode;
                currentNode=nextNode;
                if(currentNode->left)
                    que.push(currentNode->left);
                if(currentNode->right)
                    que.push(currentNode->right);
            }
            currentNode->next=NULL;
        }
    }

思路2：

每层都用一个levlHead节点来把，下一层连接起来，然后通过levelHead的next 向下遍历

    void connect(TreeLinkNode *root) {
        if(root==NULL)
            return;
        while(root){
            TreeLinkNode* levelHead=new TreeLinkNode(-1); //next指向下一层的第一个节点
            TreeLinkNode* p=root;
            TreeLinkNode* pre=levelHead;
            while(p){
                if(p->left){
                    pre->next=p->left;
                    pre=pre->next;
                }
                if(p->right){
                    pre->next=p->right;
                    pre=pre->next;
                }
                p=p->next;
            }
            pre->next=NULL;
            root=levelHead->next;//向下遍历
        }
    }

思路三：

只要左子树存在，就让左子树的节点指向右孩子，右孩子的节点指向，他兄弟节点的左孩子

    void connect(TreeLinkNode *root) {
        if(root==NULL)
            return;
        TreeLinkNode* p=root;
        TreeLinkNode* q;
        while(p->left){
            q=p;
            while(q){
                q->left->next=q->right;
                if(q->next)
                	q->right->next=q->next->left;
                q=q->next;
            }
            p=p->left;
        }
    }