leetcode:116. 填充每个节点的下一个右侧节点指针
题目
给定一个 完美二叉树 ,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next
指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next
指针设置为 NULL
。
初始状态下,所有 next
指针都被设置为 NULL
。
示例 1:
输入:root = [1,2,3,4,5,6,7]
输出:[1,#,2,3,#,4,5,6,7,#]
解释:给定二叉树如图 A 所示,你的函数应该填充它的每个 next 指针,以指向其下一个右侧节点,如图 B 所示。序列化的输出按层序遍历排列,同一层节点由 next 指针连接,'#' 标志着每一层的结束。
示例 2:
输入:root = []
输出:[]
解答 & 代码
解法一:BFS 层序遍历
/*
// 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;
queue<Node*> nodeQ;
nodeQ.push(root);
while(!nodeQ.empty())
{
int levelSize = nodeQ.size();
for(int i = 0; i < levelSize; ++i)
{
Node* cur = nodeQ.front();
nodeQ.pop();
// 填充当前节点的 next 指针
// - 如果当前节点不是这一层的最后一个节点,则将 next 指向其右侧节点
// - 否则,当前节点是这一层的最后一个节点,next 设为 NULL
cur->next = i == levelSize - 1 ? NULL : nodeQ.front();
if(cur->left != NULL)
nodeQ.push(cur->left);
if(cur->right != NULL)
nodeQ.push(cur->right);
}
}
return root;
}
};
复杂度分析:设二叉树共 N 个节点
- 时间复杂度 O(N):遍历每个节点一次
- 空间复杂度 O(N):队列
nodeQ
中存储的节点个数不会超过 N
执行结果:
执行结果:通过
执行用时:28 ms, 在所有 C++ 提交中击败了 6.31% 的用户
内存消耗:16.6 MB, 在所有 C++ 提交中击败了 44.29% 的用户
解法二:DFS
题目要将每层的节点都串成一个链表。
如何将题目的要求细化成每个节点需要做的事情?
- 如果 DFS 函数只传入一个节点
**root**
,我们只能让它的左子节点指向右子节点,但不能让root
的右子节点指向root
的兄弟节点的左子节点。也就是说,无法连接不同父节点的两个相邻节点。 - 解决办法:DFS 函数传入两个相邻节点
题目的要求就细化成了:将每两个相邻节点都连接起来 ```cpp / // 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 { private: // DFS,传入两个相邻节点 root1 和 root2,递归将这两棵树的相邻节点都连接起来 void connectTwoNode(Node root1, Node root2) { // 递归结束条件:有一个节点为 NULL,说明当前已在最后一层(完美二叉树),不用再往下层递归 if(root1 == NULL || root2 == NULL) return;
// 前序位置:连接传入的两个节点
root1->next = root2;
// 递归
// 连接相同父节点的两个相邻节点
connectTwoNode(root1->left, root1->right);
connectTwoNode(root2->left, root2->right);
// 连接不同父节点的两个相邻节点
connectTwoNode(root1->right, root2->left);
}
public: Node connect(Node root) { if(root == NULL) return root; connectTwoNode(root->left, root->right); return root; } };
复杂度分析:设二叉树共 N 个节点
- 时间复杂度 O(N):遍历每个节点一次
- 空间复杂度 O(log N):栈空间取决于递归深度,即二叉树的高度
执行结果:
执行结果:通过
执行用时:20 ms, 在所有 C++ 提交中击败了 54.53% 的用户 内存消耗:16.4 MB, 在所有 C++ 提交中击败了 77.31% 的用户 ```