116填充每个节点的下一个右侧节点指针
/* // 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) {} }; */ class Solution { public: Node* connect(Node* root) { Node* result; Node* node ; //迭代节点 queue<Node* > my_que; //队列 if(root == nullptr) return root; else // 根节点进队列 { my_que.push(root); } while(my_que.empty() != 1) { int size = my_que.size(); for(int i=0 ; i<size ; i++) { node = my_que.front(); //该层级的点弹出放入数组 my_que.pop(); if(i<size-1)//如果该节点不是该层次的最后一个，next指针连接下一个 { node->next = my_que.front(); }else//该节点是该层次的最后一个，next连接空 { node->next = nullptr; } //每一个弹出点的下一个层级左右节点压入队列 if(node->left != nullptr) my_que.push(node->left); if(node->right != nullptr) my_que.push(node->right); } } return root; } };
117填充每个节点的下一个右侧节点指针II
和116区别是一个是完全二叉树，一个不是。代码完全一致
二刷
/* // 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) {} }; */ class Solution { public: Node* connect(Node* root) { queue<Node*> my_que; if( root == nullptr ) return root; else my_que.push(root); while(my_que.size() != 0) { int size = my_que.size(); for(int i=0 ; i<size ;i++) { Node* tmp_node = my_que.front(); my_que.pop(); if(i == size-1) tmp_node->next = nullptr; else tmp_node->next = my_que.front(); if(tmp_node->left != nullptr) my_que.push(tmp_node->left); if(tmp_node->right != nullptr) my_que.push(tmp_node->right); } } return root; } };
