题目链接
https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii/
题目大意
给定一个二叉树
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
进阶：
你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
给一颗二叉树，要求每个节点与最右边的节点相连接，注意区别：这题和116题意思不太相同，116题还可以保证每个节点的左右子树都存在（除非叶子节点）。
其次，本题难点还在于要求常数的内存空间，这就排除了使用队列进行层次遍历的做法
最后，本题对于递归遍历的顺序还有要求：即需要先遍历右子树，再遍历左子树
在这幅图中，如果先遍历左子树，再遍历右子树，那么从9---1之间的指针在遍历以2为根节点的左子树时没有被连接，这样会造成以7为根节点的右子树0，无法找到右边相邻的8
//本题将条件限制为 二叉树
//与116题注意区分，不一定左子树存在
//注意递归左右子树的区别
class Solution {
public:
Node *getnext(Node *root){
if(!root) return root;
if(root->left) return root->left;
if(root->right) return root->right;
return getnext(root->next);
}
Node* connect(Node* root) {
if(!root) return root;
if(root->left && root->right) root->left->next=root->right;
if(root->left && !root->right) root->left->next=getnext(root->next);
if(root->right) root->right->next=getnext(root->next); //无论左子树是否为空，均需要找到相邻的右子树
// if(!root->left && root->right) root->right->next=getnext(root->next);
connect(root->right);
connect(root->left);
return root;
}
}
初次的做法：
Node* connect(Node* root) {//注意需要判空 节点位置的信息可能为空
//怎么维护左边起的第二个节点？？
// if(!root || !root->left) return root;
if(!root) return root;
if(root->left){
Node *tmp=NULL, *start=root;
if(start->right) tmp=start->right;
else{
while(start->next){
if(start->next->left) {
tmp=start->next->left;
break;
}
else if(start->next->right){
tmp=start->next->right;
break;
}
else{
start=start->next;
}
}
}
root->left->next=tmp;
}
if(root->next){
if(root->right){
if(root->next->left)
root->right->next=root->next->left;
else
root->right->next=root->next->right;
}
}
connect(root->right);
connect(root->left);
return root;
}
