leetcode116. 填充每个节点的下一个右侧节点指针
程序员文章站
2022-05-20 20:23:36
...
题目:给定一个完美二叉树,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。初始状态下,所有 next 指针都被设置为 NULL。
方法1. 递归常数空间
public Node connect(Node root) {
if (root == null) return null;
Node leftNode = root.left, rightNode = root.right;
// 把二叉树劈成两半, 在while循环里完成连接工作
while (leftNode != null) {
leftNode.next = rightNode;
leftNode = leftNode.right; //左节点的右儿子 连接上 右节点的左儿子
rightNode = rightNode.left;//根据完全二叉树的特性,不用rightNode判空
}
connect(root.left);
connect(root.right);
return root;
}
方法2. 队列层次遍历 非常数空间
public Node connect(Node root) {
Queue<Node> que = new LinkedList<Node>();
if(root == null) return null;
que.offer(root);
int curCount, nextCount = 1;
while (que.size() != 0) {
Node rightNode = null;
curCount = nextCount;
nextCount = 0;
while (que.size() != 0 && curCount-- > 0) {
Node leftNode = que.poll(); // 左节点出队,
leftNode.next = rightNode; // 左节点next指向右边节点
rightNode = leftNode; // 右边节点更新为当前左节点(横向 平行向左移动)
if (leftNode.right != null) { // 从 右往左 入队列
que.offer(leftNode.right);
nextCount++;
}
if (leftNode.left != null) {
que.offer(leftNode.left);
nextCount++;
}
}
}
return root;
}
下一篇: 144. 二叉树的前序遍历
推荐阅读
-
剑指offer25:复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),结果返回复制后复杂链表的head。
-
剑指offer25:复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),结果返回复制后复杂链表的head。
-
C++实现LeetCode(117.每个节点的右向指针之二)
-
填充每个节点的下一个右侧节点指针 II
-
117. 填充每个节点的下一个右侧节点指针 II
-
【C语言 LeetCode 116】填充每个节点的下一个右侧节点指针
-
leetcode116. 填充每个节点的下一个右侧节点指针
-
leetcode117. 填充每个节点的下一个右侧节点指针 II
-
leetcode116. 填充每个节点的下一个右侧节点指针/层次遍历
-
leetcode116. 填充每个节点的下一个右侧节点指针