【每日一题Day367】LC117填充每个节点的下一个右侧节点指针II | BFS

简介: 【每日一题Day367】LC117填充每个节点的下一个右侧节点指针II | BFS
117.填充每个节点的下一个右侧节点指针II

给定一个二叉树:

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

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

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

与LC116的区别在于,这个二叉树可能不是完全二叉树

  • BFS:使用队列进行BFS
/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;
    public Node() {}
    public Node(int _val) {
        val = _val;
    }
    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/
class Solution {
 public Node connect(Node root) {
        if (root == null)
            return root;
        //cur我们可以把它看做是每一层的链表
        Node cur = root;
        while (cur != null) {
            //遍历当前层的时候,为了方便操作在下一
            //层前面添加一个哑结点(注意这里是访问
            //当前层的节点,然后把下一层的节点串起来)
            Node dummy = new Node(0);
            //pre表示访下一层节点的前一个节点
            Node pre = dummy;
            //然后开始遍历当前层的链表
            while (cur != null) {
                if (cur.left != null) {
                    //如果当前节点的左子节点不为空,就让pre节点
                    //的next指向他,也就是把它串起来
                    pre.next = cur.left;
                    //然后再更新pre
                    pre = pre.next;
                }
                //同理参照左子树
                if (cur.right != null) {
                    pre.next = cur.right;
                    pre = pre.next;
                }
                //继续访问这样行的下一个节点
                cur = cur.next;
            }
            //把下一层串联成一个链表之后,让他赋值给cur,
            //后续继续循环,直到cur为空为止
            cur = dummy.next;
        }
        return root;
    }
}

迭代遍历

  1. 设置节点cur,遍历每一层的链表
  2. 设置节点pre,将下一层的节点串起来
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)
/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;
    public Node() {}
    public Node(int _val) {
        val = _val;
    }
    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/
class Solution {
 public Node connect(Node root) {
        if (root == null)
            return root;
        //cur我们可以把它看做是每一层的链表
        Node cur = root;
        while (cur != null) {
            //遍历当前层的时候,为了方便操作在下一
            //层前面添加一个哑结点(注意这里是访问
            //当前层的节点,然后把下一层的节点串起来)
            Node dummy = new Node(0);
            //pre表示访下一层节点的前一个节点
            Node pre = dummy;
            //然后开始遍历当前层的链表
            while (cur != null) {
                if (cur.left != null) {
                    //如果当前节点的左子节点不为空,就让pre节点
                    //的next指向他,也就是把它串起来
                    pre.next = cur.left;
                    //然后再更新pre
                    pre = pre.next;
                }
                //同理参照左子树
                if (cur.right != null) {
                    pre.next = cur.right;
                    pre = pre.next;
                }
                //继续访问这样行的下一个节点
                cur = cur.next;
            }
            //把下一层串联成一个链表之后,让他赋值给cur,
            //后续继续循环,直到cur为空为止
            cur = dummy.next;
        }
        return root;
    }
}


目录
相关文章
10_填充每个节点的下一个右侧节点指针
10_填充每个节点的下一个右侧节点指针
|
6月前
|
存储 SQL 算法
LeetCode 题目 117:填充每个节点的下一个右侧节点指针 II
LeetCode 题目 117:填充每个节点的下一个右侧节点指针 II
|
6月前
|
存储 SQL 算法
LeetCode 题目 116:填充每个节点的下一个右侧节点指针
LeetCode 题目 116:填充每个节点的下一个右侧节点指针
|
7月前
|
存储 C语言
链表—初始化指针变和创建新的节点------区别应用分析
链表—初始化指针变和创建新的节点------区别应用分析
力扣117 填充每个节点的下一个右侧节点指针II
力扣117 填充每个节点的下一个右侧节点指针II
|
6月前
|
C语言
指针进阶(C语言终)
指针进阶(C语言终)
|
2月前
|
C语言
无头链表二级指针方式实现(C语言描述)
本文介绍了如何在C语言中使用二级指针实现无头链表,并提供了创建节点、插入、删除、查找、销毁链表等操作的函数实现,以及一个示例程序来演示这些操作。
29 0
|
3月前
|
存储 人工智能 C语言
C语言程序设计核心详解 第八章 指针超详细讲解_指针变量_二维数组指针_指向字符串指针
本文详细讲解了C语言中的指针,包括指针变量的定义与引用、指向数组及字符串的指针变量等。首先介绍了指针变量的基本概念和定义格式,随后通过多个示例展示了如何使用指针变量来操作普通变量、数组和字符串。文章还深入探讨了指向函数的指针变量以及指针数组的概念,并解释了空指针的意义和使用场景。通过丰富的代码示例和图形化展示,帮助读者更好地理解和掌握C语言中的指针知识。
|
4月前
|
C语言
【C初阶——指针5】鹏哥C语言系列文章,基本语法知识全面讲解——指针(5)
【C初阶——指针5】鹏哥C语言系列文章,基本语法知识全面讲解——指针(5)
|
4月前
|
C语言
【C初阶——指针4】鹏哥C语言系列文章,基本语法知识全面讲解——指针(4)
【C初阶——指针4】鹏哥C语言系列文章,基本语法知识全面讲解——指针(4)