leetcode.116.117(填充每个节点的下一个右侧节点指针III)

mac2025-02-17  9

116题目描述: 给定一个完美二叉树,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下: struct Node { int val; Node *left; Node *right; Node *next; } 填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。 初始状态下,所有 next 指针都被设置为 NULL。

方法一:递归 从评论中找到一个简单易懂的方法,拉拉链法 大概总结出来递归的感觉: 需要重复某一种情况很多次的时候,就需要使用递归了。 先把最开始要解决的,进入循环之前的情况解决了。最后使用递归让他循环即可。

class Solution { public: Node* connect(Node* root) { if (root==NULL)return root; Node* left=root->left; Node* right=root->right; while(left){ left->next=right; left=left->right; right=right->left; } connect(root->left); connect(root->right); return root; } };

方法二:迭代 主要是使用广度优先算法思想

class Solution { public: Node* connect(Node* root) { if (root==NULL)return root; Node *pre=root; Node *cur=NULL; while(pre->left){ cur=pre; while(cur){ cur->left->next=cur->right; if(cur->next){ cur->right->next=cur->next->left; } cur=cur->next; } pre=pre->left; } return root; } };

117题目减少了完美二叉树的设定 方法一:迭代: 类似于116的方法,主要是要对树从右往左设定NEXT

class Solution { public: Node* connect(Node* root) { if(root==NULL)return root; queue<Node*>dl; dl.push(root); while(!dl.empty()){ int size=dl.size(); Node*pre=NULL; for(int i=0;i<size;i++){ Node*cur=dl.front(); if(cur->right)dl.push(cur->right); if(cur->left)dl.push(cur->left); cur->next=pre; pre=cur; dl.pop(); } } return root; } };
最新回复(0)