LeetCode 117. 填充每个节点的下一个右侧节点指针2
原题链接
中等
作者:
大明湖的鱼
,
2021-01-30 00:16:02
,
所有人可见
,
阅读 278
注意为什么要先递归right再递归left,是因为在找left的next时需要右边已经全连接好了,不然会找不到
/*
// 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) {
if(root == NULL) return root;
if(root->left){
if(root->right) root->left->next = root->right;
else root->left->next = findNext(root->next);
}
if(root->right){
root->right->next = findNext(root->next);
}
connect(root->right);
connect(root->left);
return root;
}
Node* findNext(Node* node){
if(node == NULL) return NULL;
if(node->left) return node->left;
if(node->right) return node->right;
if(node->next) return findNext(node->next);
return NULL;
}
};