LeetCode 117 Populating Next Right Pointers in Each Node II
程序员文章站
2022-04-27 08:51:12
...
LeetCode 117
Populating Next Right Pointers in Each Node II
-
Problem Description:
对于给定的二叉树的任意节点,如果不是所在层的最右节点,则其next指针指向其右侧节点;如果是所在层的最右节点,则其next指针指向NULL。
具体的题目信息:
https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/description/ - Example:
- Solution:
- 解题思路:用
pre
指向第一次访问的节点,用cur
指向第二次访问的节点,如果这两个指针同时存在,用pre->next = cur
将两个节点横向连接起来,并移动指针使得pre = cur, cur = NULL
。 - 编程实现:
- 解题思路:用
/**
* Definition for binary tree with next pointer.
* struct TreeLinkNode {
* int val;
* TreeLinkNode *left, *right, *next;
* TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
* };
*/
class Solution {
public:
void connect(TreeLinkNode *root) {
if (root == NULL) return;
int front = -1, rear = -1;
int last = 0;
TreeLinkNode* node[6000];
node[++rear] = root;
TreeLinkNode* p;
TreeLinkNode* pre = NULL;
TreeLinkNode* cur = NULL;
while(front < rear) {
p = node[++front];
if (pre == NULL) {
pre = p;
} else {
cur = p;
}
if (p->left) {
node[++rear] = p->left;
}
if (p->right) {
node[++rear] = p->right;
}
if (cur != NULL) {
pre->next = cur;
pre = cur;
cur = NULL;
}
if (front == last) {
pre->next = cur;
pre = NULL;
last = rear;
}
}
}
};
- 一点疑惑:不知道为什么这道题目Leetcode上没有
Run Code
的编译按钮,而且Leetcode的debug环境好像有点问题,在调试过程中一直报编译错误但是提交之后却accept了。
推荐阅读
-
【leetcode】117. 填充每个节点的下一个右侧节点指针 II(populating-next-right-pointers-in-each-node-ii)(bfs)[中等]
-
leetcode 116. populating-next-right-pointers-in-each-node 填充每个节点的下一个右侧节点指针 python3
-
【LeetCode-cpp】【48】116. 中等 填充每个节点的下一个右侧节点指针 Populating Next Righ Pointers in Each Node
-
LeetCode 117 Populating Next Right Pointers in Each Node II