您现在的位置是:首页 >技术交流 >LeetCode 117. 填充每个节点的下一个右侧节点指针 II网站首页技术交流

LeetCode 117. 填充每个节点的下一个右侧节点指针 II

夜已如歌_ok 2024-06-17 16:40:15
简介LeetCode 117. 填充每个节点的下一个右侧节点指针 II

117. 填充每个节点的下一个右侧节点指针 II

描述

给定一个二叉树:

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

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

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

示例

示例1
示例1

输入:root = [1,2,3,4,5,null,7]
输出:[1,#,2,3,#,4,5,7,#]
解释:给定二叉树如图 A 所示,你的函数应该填充它的每个 next 指针,以指向其下一个右侧节点,如图 B 所示。序列化输出按层序遍历顺序(由 next 指针连接),‘#’ 表示每层的末尾。

示例2

输入:root = []
输出:[]

链接

https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii/

解题思路

思路一: 层次遍历

LeetCode 116. 填充每个节点的下一个右侧节点指针解题一模一样。

  • 首先根元素入队
  • 当队列不为空的时候
  • 求当前队列的长度length
  • 依次从队列中取 length个元素进行处理, 先取出队列中的第一个节点node,当node不是最后一个时,将node.next指向队列的第一个,然后进入下一次迭代
/**
 * @param {Node} root
 * @return {Node}
 */
var connect = function(root) {
    if (root == null) return root;
    let queue = [root];
    while(queue.length) {
        let len = queue.length;
        for (let i = 0; i < len; i++) {
            let node = queue.shift();
            if (i < len - 1) {
                node.next = queue[0];
            } 
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }  
    }
    return root;
};

时间复杂度: O(n), 其中 n 是二叉树的节点数
空间复杂度: O(n)

思路二: 使用哑节点

新建哑结点, 方便把下一层的节点串起来

实现代码如下:

/**
 * @param {Node} root
 * @return {Node}
 */ 
var connect = function(root) {
    if (root === null) return root; 
    let cur = root;
    while (cur != null) {
        // 新建哑结点 方便把下一层的节点串起来
        let dummy = new Node(0), prev = dummy;
        while (cur != null) {
            // 如果当前节点的左子节点不为空,就让pre节点的next指向它
            if (cur.left != null) {
                prev.next = cur.left;
                prev = prev.next;
            }
            if (cur.right != null) {
                prev.next = cur.right;
                prev = prev.next;
            }
            // 指针向后移动
            cur = cur.next;
        }
        // 把下一层串联成一个链表之后,让他赋值给cur,后续继续循环,直到cur为空为止
        cur = dummy.next;
    }
    return root;
} 

参考资料

https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii/solution/bfsjie-jue-zui-hao-de-ji-bai-liao-100de-yong-hu-by/

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。