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

LeetCode 116: 填充每个节点的下一个右侧节点指针

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

题目:

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

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

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.

示例:

img

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

提示:

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

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.

提示:

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

解题思路:

最简单的方法就是层序遍历二叉树,把各个结点的next指针按要求连起来即可。题目要求不允许占用额外空间,但是递归空间占用不算在内,所以可以递归方法的层序遍历解题,很简单可以参考之前的文章:

二叉数的层序遍历

这里介绍另一种巧妙的解法:利用已构建的next指针解题。

核心思路只有两个:

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

即:

node.left.next=node.right;
node.right.next=node.next.left;

剩下的无非就是判断该结点是否为空结点,或值是否为该层结点的最后一个结点,而后进入下一层重复操作。

Java:

class Solution {
    public Node connect(Node root) {
        if(root == null)
            return root;
        // 记录每层的最左结点,该层遍历结束后利用最左侧结点进入下一层
        Node most_left = root;
        Node node = root;
        while(most_left.left!=null){// 最左侧结点的下一层只要存在结点,则继续操作
            if(node.left != null)
                node.left.next=node.right;
            if(node.next != null){ // 判断该结点是否为该层的最后一个结点
                node.right.next = node.next.left;
                node = node.next; // 刷新该结点为 next 结点
            }else{
                most_left = most_left.left; // 刷新最左侧结点
                node = most_left;
            }
        }
        return root;
    }
}

Python:

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return root
        # 记录每层的最左结点,该层遍历结束后利用最左侧结点进入下一层
        most_left = root
        node = root
        while most_left.left: # 最左侧结点的下一层只要存在结点,则继续操作
            if node.left:
                node.left.next = node.right
            if node.next: # 判断该结点是否为该层的最后一个结点
                node.right.next = node.next.left
                node = node.next # 刷新该结点为 next 结点
            else:
                node = most_left.left # 刷新最左侧结点
                most_left = node
        return root

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

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

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 116. 填充每个节点的下一个右侧节点指针(递归&循环)

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

    Michael阿明
  • Leetcode No.116 填充每个节点的下一个右侧节点指针(BFS)

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

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

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

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

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

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

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

    爱写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圈
  • 2021-10-08:填充每个节点的下一个右侧节点指针。给定一个

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

    福大大架构师每日一题
  • 【一天一大 lee】填充每个节点的下一个右侧节点指针 (难度:中等) - Day20201015

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

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

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

    前端小书童
  • LeetCode题解—填充二叉树节点右侧指针

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

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

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

    福大大架构师每日一题
  • 【Leetcode】116. 填充同一层的兄弟节点

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

    Leetcode名企之路
  • 打卡群刷题总结0814——二叉树展开为链表

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

    木又AI帮
  • LeetCode1-120题汇总,希望对你有点帮助!

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

    程序IT圈
  • 【LeetCode两题选手】算法类题目(8.7)

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

    看、未来
  • LeetCode-算法-广度和深度优先搜索-第8天

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

    布衣者
  • 剑指 Offer 52. 两个链表的第一个公共节点(指针法)

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

    杨鹏伟
  • LeetCode 19. 删除链表的倒数第N个节点(双指针)

    Michael阿明

扫码关注云+社区

领取腾讯云代金券