今天继续看二叉树的算法:填充每个节点的下一个右侧节点指针
给定一个 完美二叉树 ,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。
初始状态下,所有 next 指针都被设置为 NULL。
题目什么意思呢?就是把完全二叉树的么一行用指针进行连接,类似这样:
1 -> null
/ \
2 -> 3 -> null
/ \ / \
4-> 5->6->7 -> null
所以我首先想到的办法就是遍历,用深度优先遍历每一层树结构,然后用集合存储再一一连接:
public Node connect(Node root) {
if(root==null) {
return root;
}
//每一层都用queue保存
LinkedList<Node> queue = new LinkedList<Node>();
queue.add(root);
//开始遍历树结构,当queue为空则遍历结束
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;
}
这种解法就比较清晰,每次遍历树的一层结构,然后进行连接
时间复杂度:O(n) 空间复杂度:O(n)
如果不用到单独的列表,也就是用常量级的空间可以完成这一题吗?
不用到列表辅助,如果一层只有两个节点,那么就可以写成:
root.left.next = root.right;
那对于一层多个节点,比如4个节点,8个节点的情况,就要垮父节点操作,这时候我们就要用到父节点的next进行遍历:
if (parenthead.next != null) {
parenthead.right.next = parenthead.next.left;
}
所以,就能得出新的解法:
class Solution {
public Node connect(Node root) {
if (root == null) {
return root;
}
// 从根节点开始
Node leftmost = root;
//遍历每一层,直到没有下层节点
while (leftmost.left != null) {
Node head = leftmost;
//遍历当前这一层
while (head != null) {
// 连接第一个小树
head.left.next = head.right;
// 链接第二个小树,根据父节点的next
if (head.next != null) {
head.right.next = head.next.left;
}
// 指针向后移动
head = head.next;
}
// 去下一层的最左的节点
leftmost = leftmost.left;
}
return root;
}
}
时间复杂度:O(n) 空间复杂度:O(1)
还有一种解法,就是递归,我们可以设计一种递归方法,每次传入两个节点,并且相连:
void connectTwo(Node node1, Node node2) {
if (node1 == null || node2 == null) {
return;
}
// 将传入的两个节点连接
node1.next = node2;
}
然后调用递归方法的场景无非就是两个树结构,所以涉及到三种场景:
所以得出以下解法:
public Node connect(Node root) {
if(root==null) return null;
connectTwo(root.left,root.right);
return root;
}
public void connectTwo(Node root1,Node root2) {
if(root1==null)return;
root1.next=root2;
connectTwo(root1.left,root1.right);
connectTwo(root1.right,root2.left);
connectTwo(root2.left,root2.right);
}
还可以对第二种场景,也就是树1的右节点连接树2的左节点进行优化,将两颗树的处理放到递归方法里面:
public Node connect(Node root) {
if(root==null) return null;
connection(root);
return root;
}
public void connection(Node root){
if(root.left == null) return;
root.left.next=root.right;
if(root.next != null){
root.right.next=root.next.left;
}
connection(root.left);
connection(root.right);
}
假设树的高度为h。
时间复杂度:O(n) 空间复杂度:O(h)
https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node https://labuladong.gitee.io
感谢大家的阅读,有一起学习的小伙伴可以关注下公众号—
码上积木
❤️ 每日一个知识点,建立完整体系架构。