Medium

题目描述

给定一个完美的二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

示例 1：

输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。

示例 2：

输入：root = []
输出：[]

约束条件：

  • 树中节点的数量在 [0, 2^12 - 1] 范围内
  • -1000 <= Node.val <= 1000

进阶：

  • 你只能使用常量级额外空间。
  • 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

解题思路

这道题有多种解法，主要思路如下：

方法一：层序遍历（BFS） 最直观的思路是使用队列进行层序遍历。对于每一层，我们将节点从左到右依次连接。虽然简单易懂，但需要 O(n) 的额外空间。

方法二：利用已建立的 next 指针（推荐） 由于题目给定的是完美二叉树，我们可以利用上一层已经建立好的 next 指针来为下一层建立连接。这是最优解法，只需要 O(1) 的额外空间。

具体思路：

  1. 从根节点开始，逐层处理
  2. 对于每一层，从最左边的节点开始遍历
  3. 对于当前节点，连接其左右子树：左子树的 next 指向右子树
  4. 如果当前节点有 next 指针，则当前节点的右子树 next 指向下一个节点的左子树
  5. 移动到下一层继续处理

方法三：递归 利用递归的思路，对于每个节点，先处理其子节点的连接，然后递归处理左右子树。

由于完美二叉树的特殊性质，方法二是最优解，既满足常量空间要求，又具有良好的时间复杂度。

代码实现

class Solution {
public:
    Node* connect(Node* root) {
        if (!root) return root;
        
        Node* leftmost = root;
        
        // 逐层处理，直到叶子节点的上一层
        while (leftmost->left) {
            Node* head = leftmost;
            
            // 遍历当前层的所有节点
            while (head) {
                // 连接左子树和右子树
                head->left->next = head->right;
                
                // 如果有下一个节点，连接当前节点的右子树和下个节点的左子树
                if (head->next) {
                    head->right->next = head->next->left;
                }
                
                head = head->next;
            }
            
            // 移动到下一层
            leftmost = leftmost->left;
        }
        
        return root;
    }
};

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        if not root:
            return root
        
        leftmost = root
        
        # 逐层处理，直到叶子节点的上一层
        while leftmost.left:
            head = leftmost
            
            # 遍历当前层的所有节点
            while head:
                # 连接左子树和右子树
                head.left.next = head.right
                
                # 如果有下一个节点，连接当前节点的右子树和下个节点的左子树
                if head.next:
                    head.right.next = head.next.left
                
                head = head.next
            
            # 移动到下一层
            leftmost = leftmost.left
        
        return root

public 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;
                
                // 如果有下一个节点，连接当前节点的右子树和下个节点的左子树
                if (head.next != null) {
                    head.right.next = head.next.left;
                }
                
                head = head.next;
            }
            
            // 移动到下一层
            leftmost = leftmost.left;
        }
        
        return root;
    }
}

var connect = function(root) {
    if (!root) return root;
    
    let leftmost = root;
    
    // 逐层处理，直到叶子节点的上一层
    while (leftmost.left) {
        let head = leftmost;
        
        // 遍历当前层的所有节点
        while (head) {
            // 连接左子树和右子树
            head.left.next = head.right;
            
            // 如果有下一个节点，连接当前节点的右子树和下个节点的左子树
            if (head.next) {
                head.right.next = head.next.left;
            }
            
            head = head.next;
        }
        
        // 移动到下一层
        leftmost = leftmost.left;
    }
    
    return root;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历每个节点一次，n 为节点总数
空间复杂度O(1)只使用了常量级别的额外空间，不计算递归栈空间

相关题目