leetcode-116-填充每个节点的下一个右侧节点指针

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

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, 212 - 1] 范围内
• -1000 <= node.val <= 1000

进阶：

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

解题思路-基础

根据题意可知本题要求我们把完美二叉树每一层的节点通过 next 指针进行连接，那我们就把这个要求一步步实现即可:

1. 把每一层的节点从左到右收集到一起
2. 把收集到的每一层节点按顺序连接

代码实现

var connect = function(root) {
    if(root === null){
        return null
    }

    // 前序遍历按层收集节点
    const collection = []
    function preorder(node,deep){
        if(node === null){
            return
        }
        if(!collection[deep]){
            collection[deep] = []
        }
        collection[deep].push(node)
        preorder(node.left,deep+1)
        preorder(node.right,deep+1)
    }
    preorder(root,0)
    
    // 处理每一层节点的 next指针
    for(let i = 0;i<collection.length;i++){
        const list = collection[i]
        for(let j = 0;j<list.length-1;j++){
            list[j].next = list[j+1]
        }
    }

    return root
};

解题思路-优化

上面的实现过程中，我们先进行前序遍历按层收集了所有节点，然后遍历收集到的结果数组进行连接，虽然时间复杂度是 O(n)，但实际做了两次遍历。其实我们可以通过层序遍历实现一遍遍历的同时完成 next 指针的连接。 这里有一个问题是要保证当前层的最后一个节点不要和下一层的第一个节点连接，处理这个问题要基于本题给定的条件。 因为给定的是一棵完美二叉树，所以每一层节点的数量都等于上一层的两倍，所以利用这个特性，我们就可以知道当前是否是本层最后一个节点。

代码实现

var connect = function(root) {
    if(root === null){
        return null
    }
    // 预计总节点数
    let totalNum = 1
    // 节点队列
    const queue = [root]
    // 已处理节点数量
    let num = 0
    // 上一个节点
    let pre = null
    while(queue.length){
        const current = queue.shift()
        num++

        // 如果当前是这一层最后一个，更新 totalNum
        if(num === totalNum){
            totalNum *= 2
        }else{
        // 否则连接next指针
            pre.next = current
        }
        
        pre = current

        if(current.left){
            queue.push(current.left)
        }
        if(current.right){
            queue.push(current.right)
        }
    }

    return root
};

解题思路-进阶

上面的实现方式时、空复杂度都是 O(n) O(n)，但是第二种做了进一步优化，只需要一次遍历，所以实际表现会更好一点。但是都没有达到本题进阶要求的常量级额外空间。 想要达到进阶要求，就不能收集节点再进行处理，所以就要想办法在扫描的过程中直接进行 next 指针的连接。 扫描过程中连接麻烦的是示例1中 5、6 节点的这种情况，这里我们站在上一层的视角看这个问题，如果2、3的连接已经建立，那么想要连接 5、6 其实就是 2.right.next = 2.next.left，所以我们每次站在上一层处理下一层的连接就可以实现不借助额外空间一次遍历完成层序连接了。

代码实现

var connect = function(root) {
    if (root === null) {
        return null
    }
    
    // 初始化待处理层最左侧节点
    let leftmost = root
    while (leftmost.left !== null) {
        let current = leftmost
        // 连接当前节点的左右子节点
        while (current !== null) {
            current.left.next = current.right
            // 如果当前节点的next节点存在
            if (current.next != null) {
                // 连接当前节点的右子节点和next指针的左子节点
                current.right.next = current.next.left
            }
            // 继续处理当前层节点
            current = current.next
        }
        // 处理下一层节点
        leftmost = leftmost.left
    }
    
    return root
};

至此我们就完成了 leetcode-116-填充每个节点的下一个右侧节点指针

如有任何问题或建议，欢迎留言讨论！