【一天一道LeetCode】#116. Populating Next Right Pointers in Each Node

一天一道LeetCode

（一）题目

来源：https://leetcode.com/problems/populating-next-right-pointers-in-each-node/

（二）解题

题目大意：定义一个新的二叉树结构，增加一个新指针next指向该节点右侧相邻的节点。

解题思路：考虑到要指向右侧相邻的节点，可以采用层序遍历的方式来求解

将每一层的节点用next连接起来即可！

层序遍历可以参考：【一天一道LeetCode】#102. Binary Tree Level Order Traversal

废话不说，看AC代码：

/**
 * 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) {
        if(root==NULL) return;
        queue<TreeLinkNode *> myque;
        myque.push(root);
        while(!myque.empty())
        {
            queue<TreeLinkNode *> temp_que;
            TreeLinkNode *pre = NULL;
            while(!myque.empty())
            {
                TreeLinkNode *temp = myque.front();
                myque.pop();
                if(pre==NULL) pre = temp;//相当于每一层的头节点
                else {
                    pre->next = temp;//用next指针连接每一层的节点
                    pre = temp;
                }
                if(temp->left!=NULL) temp_que.push(temp->left);//下一层
                if(temp->right!=NULL) temp_que.push(temp->right);//下一层
            }
            pre->next=NULL;//最后一个节点的next需要指向NULL
            myque=temp_que;//进入下一层操作
        }
    }
};