题目描述
这种题目的思路依然是递归。
C++：
/*
// 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) {
// *** base case
if (root == NULL){
return NULL;
}
//在根节点的next为空，且左右子树不为空的时候，
//将左节点的next指向右节点，最后把根节点的next指向null。
else if (root->next == NULL && root->left!=NULL && root->right!=NULL){
root->left->next = root->right;
root->next = NULL;
// root->next = NULL;
}
//在根节点的不为空，且左右子树不为空的时候，
//将左节点的next指向右节点，右节点的next指向根节点平行根节点的左节点；最后把根节点的next指向null。
else if (root->next!=NULL && root->left!=NULL && root->right!=NULL ){
root->left->next = root->right;
root->right->next = root->next->left;
}
// 递归
connect(root->left);
connect(root->right);
return root;
}
};
image.png
