LEETCODE 116. 填充每个节点的下一个右侧节点指针
题目描述
给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。初始状态下，所有 next 指针都被设置为 NULL。示例：输入：
{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":{"$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}
输出：
{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":{"$id":"6","left":null,"next":null,"right":null,"val":7},"right":null,"val":6},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"7","left":{"$ref":"5"},"next":null,"right":{"$ref":"6"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"7"},"val":1}
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。
提示：
你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
题目地址:
https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/
迭代解法1
回想一下二叉树的层次遍历，用广度优先实现的时候，就是层层遍历，每层临时遍历的节点都会放到一个队列中。
队列中保存了第i层节点的信息，我们利用这个特点，将队列中的元素都串联一遍就可以了。
时间复杂度:O(n)
空间复杂度:O(n)
java代码:
class Solution {
public Node connect(Node root) {
if(root==null) {
return root;
}
LinkedList<Node> queue = new LinkedList<Node>();
queue.add(root);
while(queue.size()>0) {
int size = queue.size();
//将队列中的元素串联起来
Node tmp = queue.get(0);
for(int i=1;i<size;++i) {
tmp.next = queue.get(i);
tmp = queue.get(i);
}
//遍历队列中的每个元素，将每个元素的左右节点也放入队列中
for(int i=0;i<size;++i) {
tmp = queue.remove();
if(tmp.left!=null) {
queue.add(tmp.left);
}
if(tmp.right!=null) {
queue.add(tmp.right);
}
}
}
return root;
}
}
python代码:
class Solution(object):
def connect(self, root):
"""
:type root: Node
:rtype: Node
"""
if not root:
return root
queue = [root]
while queue:
size = len(queue)
# 将队列中的元素串联起来
tmp = queue[0]
for i in xrange(1,size):
tmp.next = queue[i]
tmp = queue[i]
# 遍历队列中的每个元素，将每个元素的左右节点也放入队列中
for _ in xrange(size):
tmp = queue.pop(0)
if tmp.left:
queue.append(tmp.left)
if tmp.right:
queue.append(tmp.right)
return root
迭代解法2
题目要求是常量的辅助空间，所以第一种解法并不符合要求，下面来看下O(1)空间复杂度的实现细节。
注意，题目说的二叉树是一棵完美二叉树，即每一层的节点都是满的。
仔细看下完成后的串联树，其连接的方式有两种:
第一种是这两个串联的节点都有一个共同的父节点，通过父节点就可以将这两个子节点串联起来
第二种是这两个串联的节点的父节点不同，对于这种情况，如果我们能将这一层的上一层串联好。那么可以通过父节点的next找到邻居，完成串联。
即
root.right.next => root.next.left
这里我们需要保证root.next不为空就可以了。
也就是说当我们要串联第i层节点时，需要先完成第i-1层的节点串联
第一层最多只有一个节点，不需要串联
第二层最多只有两个节点，借助根节点就可以完成串联了
第三层串联时，上一层已经串联完了，所以第三层可以完成串联
同理，可以完成第四层，第五层，第N层的串联
时间复杂度:O(n)
空间复杂度:O(1)
java代码
class Solution {
public Node connect(Node root) {
if(root==null) {
return root;
}
Node pre = root;
//循环条件是当前节点的left不为空，当只有根节点
//或所有叶子节点都出串联完后循环就退出了
while(pre.left!=null) {
Node tmp = pre;
while(tmp!=null) {
//将tmp的左右节点都串联起来
//注:外层循环已经判断了当前节点的left不为空
tmp.left.next = tmp.right;
//下一个不为空说明上一层已经帮我们完成串联了
if(tmp.next!=null) {
tmp.right.next = tmp.next.left;
}
//继续右边遍历
tmp = tmp.next;
}
//从下一层的最左边开始遍历
pre = pre.left;
}
return root;
}
}
python代码:
class Solution(object):
def connect(self, root):
"""
:type root: Node
:rtype: Node
"""
if not root:
return root
pre = root
# 循环条件是当前节点的left不为空，当只有根节点
# 或所有叶子节点都出串联完后循环就退出了
while pre.left:
tmp = pre
while tmp:
# 将tmp的左右节点都串联起来
# 注:外层循环已经判断了当前节点的left不为空
tmp.left.next = tmp.right
# 下一个不为空说明上一层已经帮我们完成串联了
if tmp.next:
tmp.right.next = tmp.next.left
# 继续右边遍历
tmp = tmp.next
# 从下一层的最左边开始遍历
pre = pre.left
return root
递归
上面两种方式是属于横向的视角，而递归则像是一个深度的视角。
以从上往下的方向看，1，2，3，5，6这几个节点在位置上都是紧挨着的，同时这几个节点都是左右串联的。
我们以当前节root点为起始，左右节点不断的深入下面，left节点不断往右走，right节点不断往左走，当这两个节点走到底后，整个纵深这段就完成了串联。
递归函数实现如下：
-
终止条件:当前节点为空时 -
函数内:以当前节点为起始，完成从上往下的纵深串联，再递归的调用当前 left和right
时间复杂度:O(n)
空间复杂度:O(h)，h是树的高度
java代码:
class Solution {
public Node connect(Node root) {
dfs(root);
return root;
}
void dfs(Node root) {
if(root==null) {
return;
}
Node left = root.left;
Node right = root.right;
//配合动画演示理解这段，以root为起点，将整个纵深这段串联起来
while(left!=null) {
left.next = right;
left = left.right;
right = right.left;
}
//递归的调用左右节点，完成同样的纵深串联
dfs(root.left);
dfs(root.right);
}
}
python代码:
class Solution(object):
def connect(self, root):
"""
:type root: Node
:rtype: Node
"""
def dfs(root):
if not root:
return
left = root.left
right = root.right
# 配合动画演示理解这段，以root为起点，将整个纵深这段串联起来
while left:
left.next = right
left = left.right
right = right.left
# 递归的调用左右节点，完成同样的纵深串联
dfs(root.left)
dfs(root.right)
dfs(root)
return root
(全文完)
5 次阅读