给定一个 完美二叉树 ,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:
struct Node { int val; Node *left; Node *right; Node *next; }
填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL
。
初始状态下,所有 next 指针都被设置为 NULL
。
思路一:递归
struct Node* connect(struct Node* root) {
if(root==NULL)return NULL;
else if(root->left == NULL || root->right == NULL) return root;
root->left->next = root->right;
struct Node* left = root->left->right;
struct Node* right = root->right->left;
while(left!=NULL&& right!=NULL){
left->next = right;
left = left->right;
right = right->left;
}
root->left = connect(root->left);
root->right = connect(root->right);
return root;
}
分析:
本题要将每个next指针指向下一个右侧节点,可想到使用递归将左子树next指针指向right,再将右子树向下递归,最后输出root文章来源:https://www.toymoban.com/news/detail-690728.html
总结:
本题考察递归的应用,将二叉树左子树指针指向右子树即可解决文章来源地址https://www.toymoban.com/news/detail-690728.html
到了这里,关于leetcode做题笔记116. 填充每个节点的下一个右侧节点指针的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!