专栏首页爱写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 条评论
登录 后参与评论

相关文章

  • LwwtCode 173:二叉搜索树迭代器 Binary Search Tree Iterator

    Implement an iterator over a binary search tree (BST). Your iterator will be ini...

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

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

    爱写bug
  • LeetCode707:设计链表 Design Linked List

    设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性:val 和 next。val 是当前节点的值,next 是指向下一个节点的指针/引...

    爱写bug
  • 1038 一元三次方程求解

    1038 一元三次方程求解 2001年NOIP全国联赛提高组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 白银 Silver ...

    attack
  • Java 集合系列(四)—— ListIterator 源码分析

      Iterator(迭代器)是一种设计模式,是一个对象,用于遍历集合中的所有元素。   Iterator 包含四个方法,分别是:next()、hasNext(...

    那一叶随风
  • 强化学习笔记4:无模型预测 model-free prediction

    对于Env来说,不是参数已知的MDP 比如元组中a、s、P的关系不确定 or 未知

    列夫托尔斯昊
  • JVM的StackMapTable的前世今生

    在Java 6版本之后JVM在class文件中引入了栈图(StackMapTable)。

    JavaEdge
  • 『设计模式』职责链模式(Chain of Responsibility) 可怜的加薪、请假之路

    客户端发出一个请求,会有很多对象都可以来处理这个请求,而且不同对象的处理逻辑是不一样的。 对于客户端而言,无所谓谁来处理,反正有对象处理就可以了。而且在上述处...

    风骨散人Chiam
  • 腾讯云发布数据安全解决方案数盾,解决三大新痛点

    腾讯云安全
  • HanLP二元核心词典详细解析

    本文分析:HanLP版本1.5.3中二元核心词典的存储与查找。当词典文件没有被缓存时,会从文本文件CoreNatureDictionary.ngram.txt中...

    IT小白龙

扫码关注云+社区

领取腾讯云代金券