leetcode117. 填充每个节点的下一个右侧节点指针 II

题目大意

给定一个二叉树

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

解题思路

解题思路同leetcode116. 填充每个节点的下一个右侧节点指针。每层的非最后一个节点，则next指针指向队列中的第一个元素即可。

class Solution {
public:
    Node* connect(Node* root) {
        if (!root){
        	return nullptr;
        }

        Node * tmp = root;
        queue<Node*> myqueue;
        myqueue.push(root);

        while(!myqueue.empty()){
        	int length = myqueue.size();
        	for (int i = 0; i < length; ++i){
        		tmp = myqueue.front(); myqueue.pop();
        		if(tmp->left){
        			myqueue.push(tmp->left);
        		}
        		if (tmp->right){
        			myqueue.push(tmp->right);
        		}
        		if (i != length - 1){
        			tmp->next = myqueue.front();
        		}
        	}
        }
        return root;
    }
};