专栏首页爱写BugLeetCode117:填充每个节点的下一个右侧节点指针 II

LeetCode117:填充每个节点的下一个右侧节点指针 II

LeetCode117:填充每个节点的下一个右侧节点指针 II Populating Next Right Pointers in Each Node II

题目:

给定一个二叉树

Given a binary tree

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

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

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

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

Initially, all next pointers are set to NULL.

进阶:

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

Follow up:

  • You may only use constant extra space.
  • Recursive approach is fine, you may assume implicit stack space does not count as extra space for this problem.

示例:

img

输入:root = [1,2,3,4,5,null,7]
输出:[1,#,2,3,#,4,5,7,#]
解释:给定二叉树如图 A 所示,你的函数应该填充它的每个 next 指针,以指向其下一个右侧节点,如图 B 所示。

提示:

  • 树中的节点数小于 6000
  • -100 <= node.val <= 100 Constraints:
  • The number of nodes in the given tree is less than 6000.
  • -100 &lt;= node.val &lt;= 100

解题思路:

与上一题的唯一区别就是该二叉树不是完美二叉树。对于完美二叉树的思路:

  • 一个结点的左孩子的 next 指针指向该结点的右孩子
  • 一个结点的右孩子的 next 指针指向该结点的 next 结点的左孩子

不再适用,因为一个结点可能没有左孩子或者没有右孩子。只需稍微转变一下思路即可:

先设置一个头结点 temp,作为每层的最左侧结点。再设置一个前驱结点 prev = temp,该结点的 next 指针指向最邻近的右侧结点,然后刷新前驱结点:prev = prev.next 。继续查找 prev 结点最邻近的右侧结点,重复上述操作,直到该层结束。而此时 头结点 temp.next 就是下一层的最左侧结点。

Java:

class Solution {
    public Node connect(Node root) {

        if (root == null)
            return root;
        Node temp = new Node(0); // 虚拟头结点
        Node curr = root, prev = temp; // 当前结点和前驱结点

        while (curr != null) {
            if (curr.left != null) {
                prev.next = curr.left;
                prev = prev.next;
            }
            if (curr.right != null) {
                prev.next = curr.right;
                prev = prev.next;
            }
            curr = curr.next;
            // curr 为 null 时,该层连接完成。
            if (curr == null) {
                curr = temp.next; // 当前结点改为下一层的最左侧结点
                temp.next = null; // 虚拟结点 next 指针指向 null
                prev = temp; // 前驱结点重新设置为虚拟头结点
            }
        }
        return root;
    }
}

Python:

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return root
        temp = Node(0) # 虚拟头结点
        prev,curr = temp,root # 当前结点和前驱结点

        while curr:
            if curr.left:
                prev.next = curr.left
                prev = prev.next
            if curr.right:
                prev.next = curr.right
                prev = prev.next
            curr = curr.next
            # curr 为 null 时,该层连接完成
            if not curr:
                curr = temp.next # 当前结点改为下一层的最左侧结点
                temp.next = None # 虚拟结点 next 指针指向 null
                prev = temp # 前驱结点重新设置为虚拟头结点
        return root

本文分享自微信公众号 - 爱写Bug(iCodeBugs),作者:爱写Bug

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-02-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

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

    struct Node { int val; Node *left; Node *right; Node *next; } 填充它的每个 nex...

    Leetcode名企之路
  • LeetCode 116: 填充每个节点的下一个右侧节点指针

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

    爱写bug
  • LeetCode 117. 填充每个节点的下一个右侧节点指针 II(递归&循环)

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

    Michael阿明
  • ​LeetCode刷题实战117:填充每个节点的下一个右侧节点指针 II

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

    程序IT圈
  • Leetcode No.116 填充每个节点的下一个右侧节点指针(BFS)

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

    week
  • 2021-10-08:填充每个节点的下一个右侧节点指针。给定一个

    2021-10-08:填充每个节点的下一个右侧节点指针。给定一个 完美二叉树 ,其所有叶子节点都在同一层,每个父节点都有两个子节点。填充它的每个 next 指针...

    福大大架构师每日一题
  • LeetCode 116. 填充每个节点的下一个右侧节点指针(递归&循环)

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

    Michael阿明
  • ​LeetCode刷题实战116:填充每个节点的下一个右侧节点指针

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就...

    程序IT圈
  • 【一天一大 lee】填充每个节点的下一个右侧节点指针 II (难度:中等) - Day20200928

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

    前端小书童
  • 【一天一大 lee】填充每个节点的下一个右侧节点指针 (难度:中等) - Day20201015

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

    前端小书童
  • 2021-10-08:填充每个节点的下一个右侧节点指针。给定一个 完美二叉树 ,其所有叶子节点都在同一层,每个父节点都有两个子节

    2021-10-08:填充每个节点的下一个右侧节点指针。给定一个 完美二叉树 ,其所有叶子节点都在同一层,每个父节点都有两个子节点。填充它的每个 next 指针...

    福大大架构师每日一题
  • LeetCode题解—填充二叉树节点右侧指针

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

    码上积木
  • 剑指 Offer 52. 两个链表的第一个公共节点(指针法)

    思路:用两个指针分别指向A,B的头结点,然后循环遍历链表,当A遍历完后将其指向B的头结点,B遍历完后将其指向A的头结点。

    杨鹏伟
  • LeetCode1-120题汇总,希望对你有点帮助!

    时间很快,公众号发布的LeetCode题目,已经达到120道题了。今天把发布的1-120篇LeetCode文章整理一下,平时文章都放在比较末尾,阅读量都不高,相...

    程序IT圈
  • 打卡群刷题总结0814——二叉树展开为链表

    链接:https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node

    木又AI帮
  • [Leetcode][链表]相关题目汇总/分析/总结

    蛮三刀酱
  • 【LeetCode两题选手】算法类题目(8.7)

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

    看、未来
  • 【Leetcode】116. 填充同一层的兄弟节点

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

    Leetcode名企之路
  • LeetCode-算法-广度和深度优先搜索-第8天

    给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。 你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他...

    布衣者

扫码关注云+社区

领取腾讯云代金券