参与本项目,贡献其他语言版本的代码,拥抱开源,让更多学习算法的小伙伴们受益!
给定一个 完美二叉树 ,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。
初始状态下,所有 next 指针都被设置为 NULL。
进阶:
- 你只能使用常量级额外空间。
- 使用递归解题也符合要求,本题中递归程序占用的栈空间不算做额外的空间复杂度。
注意题目提示内容,:
- 你只能使用常量级额外空间。
- 使用递归解题也符合要求,本题中递归程序占用的栈空间不算做额外的空间复杂度。
基本上就是要求使用递归了,迭代的方式一定会用到栈或者队列。
一想用递归怎么做呢,虽然层序遍历是最直观的,但是递归的方式确实不好想。
如图,假如当前操作的节点是cur:
最关键的点是可以通过上一层递归 搭出来的线,进行本次搭线。
图中cur节点为元素4,那么搭线的逻辑代码:(注意注释中操作1和操作2和图中的对应关系)
if (cur->left) cur->left->next = cur->right; // 操作1
if (cur->right) {
if (cur->next) cur->right->next = cur->next->left; // 操作2
else cur->right->next = NULL;
}
理解到这里,使用前序遍历,那么不难写出如下代码:
class Solution {
private:
void traversal(Node* cur) {
if (cur == NULL) return;
// 中
if (cur->left) cur->left->next = cur->right; // 操作1
if (cur->right) {
if (cur->next) cur->right->next = cur->next->left; // 操作2
else cur->right->next = NULL;
}
traversal(cur->left); // 左
traversal(cur->right); // 右
}
public:
Node* connect(Node* root) {
traversal(root);
return root;
}
};
本题使用层序遍历是最为直观的,如果对层序遍历不了解,看这篇:二叉树:层序遍历登场!。
遍历每一行的时候,如果不是最后一个Node,则指向下一个Node;如果是最后一个Node,则指向nullptr。
代码如下:
class Solution {
public:
Node* connect(Node* root) {
queue<Node*> que;
if (root != nullptr) que.push(root);
while (!que.empty()) {
int size = que.size();
for (int i = 0; i < size; ++i) {
Node* node = que.front();
que.pop();
if (i != size - 1) {
node->next = que.front(); //如果不是最后一个Node 则指向下一个Node
} else node->next = nullptr; //如果是最后一个Node 则指向nullptr
if (node->left != nullptr) que.push(node->left);
if (node->right != nullptr) que.push(node->right);
}
}
return root;
}
};
// 递归法
class Solution {
public void traversal(Node cur) {
if (cur == null) return;
if (cur.left != null) cur.left.next = cur.right; // 操作1
if (cur.right != null) {
if(cur.next != null) cur.right.next = cur.next.left; //操作2
else cur.right.next = null;
}
traversal(cur.left); // 左
traversal(cur.right); //右
}
public Node connect(Node root) {
traversal(root);
return root;
}
}
// 迭代法
class Solution {
public Node connect(Node root) {
if (root == null) return root;
Queue<Node> que = new LinkedList<Node>();
que.offer(root);
Node nodePre = null;
Node node = null;
while (!que.isEmpty()) {
int size = que.size();
for (int i=0; i<size; i++) { // 开始每一层的遍历
if (i == 0) {
nodePre = que.peek(); // 记录一层的头结点
que.poll();
node = nodePre;
} else {
node = que.peek();
que.poll();
nodePre.next = node; // 本层前一个节点next指向本节点
nodePre = nodePre.next;
}
if (node.left != null) que.offer(node.left);
if (node.right != null) que.offer(node.right);
}
nodePre.next = null; // 本层最后一个节点指向null
}
return root;
}
}
// 迭代法
class Solution {
public Node connect(Node root) {
if (root == null) {
return root;
}
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
// 每层的第一个节点
Node cur = queue.poll();
if (cur.left != null) {
queue.add(cur.left);
}
if (cur.right != null) {
queue.add(cur.right);
}
// 因为已经移除了每层的第一个节点,所以将 0 改为 1
while (size-- > 1) {
Node next = queue.poll();
if (next.left != null) {
queue.add(next.left);
}
if (next.right != null) {
queue.add(next.right);
}
// 当前节点指向同层的下一个节点
cur.next = next;
// 更新当前节点
cur = next;
}
// 每层的最后一个节点不指向 null 在力扣也能过
cur.next = null;
}
return root;
}
}
# 递归法
class Solution:
def connect(self, root: 'Node') -> 'Node':
def traversal(cur: 'Node') -> 'Node':
if not cur: return []
if cur.left: cur.left.next = cur.right # 操作1
if cur.right:
if cur.next:
cur.right.next = cur.next.left # 操作2
else:
cur.right.next = None
traversal(cur.left) # 左
traversal(cur.right) # 右
traversal(root)
return root
# 迭代法
class Solution:
def connect(self, root: 'Node') -> 'Node':
if not root: return
res = []
queue = [root]
while queue:
size = len(queue)
for i in range(size): # 开始每一层的遍历
if i==0:
nodePre = queue.pop(0) # 记录一层的头结点
node = nodePre
else:
node = queue.pop(0)
nodePre.next = node # 本层前一个节点next指向本节点
nodePre = nodePre.next
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
nodePre.next = None # 本层最后一个节点指向None
return root
// 迭代法
func connect(root *Node) *Node {
if root == nil {
return root
}
stack := make([]*Node, 0)
stack = append(stack, root)
for len(stack) > 0 {
n := len(stack) // 记录当前层节点个数
for i := 0; i < n; i++ {
node := stack[0] // 依次弹出节点
stack = stack[1:]
if i == n - 1 { // 如果是这层最右的节点,next指向nil
node.Next = nil
} else {
node.Next = stack[0] // 如果不是最右的节点,next指向右边的节点
}
if node.Left != nil { // 如果存在左子节点,放入栈中
stack = append(stack, node.Left)
}
if node.Right != nil { // 如果存在右子节点,放入栈中
stack = append(stack, node.Right)
}
}
}
return root
}
// 常量级额外空间,使用next
func connect(root *Node) *Node {
if root == nil {
return root
}
for cur := root; cur.Left != nil; cur = cur.Left { // 遍历每层最左边的节点
for node := cur; node != nil; node = node.Next { // 当前层从左到右遍历
node.Left.Next = node.Right // 左子节点next指向右子节点
if node.Next != nil { //如果node next有值,右子节点指向next节点的左子节点
node.Right.Next = node.Next.Left
}
}
}
return root
}
const connect = root => {
if (!root) return root;
// 根节点入队
const Q = [root];
while (Q.length) {
const len = Q.length;
// 遍历这一层的所有节点
for (let i = 0; i < len; i++) {
// 队头出队
const node = Q.shift();
// 连接
if (i < len - 1) {
// 新的队头是node的右边元素
node.next = Q[0];
}
// 队头左节点有值,放入队列
node.left && Q.push(node.left);
// 队头右节点有值,放入队列
node.right && Q.push(node.right);
}
}
return root;
};
(注:命名空间‘Node’与typescript中内置类型冲突,这里改成了‘NodePro’)
递归法:
class NodePro {
val: number
left: NodePro | null
right: NodePro | null
next: NodePro | null
constructor(val?: number, left?: NodePro, right?: NodePro, next?: NodePro) {
this.val = (val === undefined ? 0 : val)
this.left = (left === undefined ? null : left)
this.right = (right === undefined ? null : right)
this.next = (next === undefined ? null : next)
}
}
function connect(root: NodePro | null): NodePro | null {
if (root === null) return null;
root.next = null;
recur(root);
return root;
};
function recur(node: NodePro): void {
if (node.left === null || node.right === null) return;
node.left.next = node.right;
node.right.next = node.next && node.next.left;
recur(node.left);
recur(node.right);
}
迭代法:
class NodePro {
val: number
left: NodePro | null
right: NodePro | null
next: NodePro | null
constructor(val?: number, left?: NodePro, right?: NodePro, next?: NodePro) {
this.val = (val === undefined ? 0 : val)
this.left = (left === undefined ? null : left)
this.right = (right === undefined ? null : right)
this.next = (next === undefined ? null : next)
}
}
function connect(root: NodePro | null): NodePro | null {
if (root === null) return null;
const queue: NodePro[] = [];
queue.push(root);
while (queue.length > 0) {
for (let i = 0, length = queue.length; i < length; i++) {
const curNode: NodePro = queue.shift()!;
if (i === length - 1) {
curNode.next = null;
} else {
curNode.next = queue[0];
}
if (curNode.left !== null) queue.push(curNode.left);
if (curNode.right !== null) queue.push(curNode.right);
}
}
return root;
};
//递归
public class Solution {
public Node Connect(Node root) {
if (root == null) {
return null;
}
ConnectNodes(root.left, root.right);
return root;
}
private void ConnectNodes(Node node1, Node node2) {
if (node1 == null || node2 == null) {
return;
}
// 将左子节点的 next 指向右子节点
node1.next = node2;
// 递归连接当前节点的左右子节点
ConnectNodes(node1.left, node1.right);
ConnectNodes(node2.left, node2.right);
// 连接跨越父节点的两个子树
ConnectNodes(node1.right, node2.left);
}
}
// 迭代
public class Solution
{
public Node Connect(Node root)
{
Queue<Node> que = new Queue<Node>();
if (root != null)
{
que.Enqueue(root);
}
while (que.Count > 0)
{
var queSize = que.Count;
for (int i = 0; i < queSize; i++)
{
var cur = que.Dequeue();
// 当这个节点不是这一层的最后的节点
if (i != queSize - 1)
{
// 当前节点指向下一个节点
cur.next = que.Peek();
}
// 否则指向空
else
{
cur.next = null;
}
if (cur.left != null)
{
que.Enqueue(cur.left);
}
if (cur.right != null)
{
que.Enqueue(cur.right);
}
}
}
return root;
}
}