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

相关文章

  • 队列和 BFS —— 栈和 DFS

    这里我们提供一个示例来说明如何使用 BFS 来找出根结点 A 和目标结点 G 之间的最短路径。

    爱写bug
  • LeetCode 106: 从中序与后序遍历序列构造二叉树

    Given inorder and postorder traversal of a tree, construct the binary tree.

    爱写bug
  • LeetCode 105: 从前序与中序遍历序列构造二叉树

    Given preorder and inorder traversal of a tree, construct the binary tree.

    爱写bug
  • 数据结构与算法笔记 cp2-2:线性表

    对于每一个元素来说,它需要存储自身信息在数据域中,还需要存储直接后继的位置信息在指针域中,这两部分信息共同构成一个结点(Node)。n 个结点就 链结成一个链表...

    Chor
  • 小文’s blog — 平衡二叉树构造方法

    神无月
  • 一元多项式的乘法与加法运算

    版权声明:本文为博主原创文章,转载请注明博客地址: https://blog.csdn.ne...

    zy010101
  • .Net自定义应用程序配置

    几乎所有的应用程序都离不开配置,有时候我们会将配置信息存在数据库中(例如大家可能常会见到名为Config这样的表);更多时候,我们会将配置写在Web.confi...

    张子阳
  • 4.5.2 平衡二叉树

    为了避免树的高度增长过快,降低二叉排序树的性能,我们规定在插入和删除二叉树结点时,要保证任意结点的左、右子树高度差的绝对值不超过1,将这样的二叉树称为平衡二叉树...

    week
  • 深入浅出分析MySQL索引设计背后的数据结构

    对于这项规定,很多研发小伙伴不理解。本文就来深入简出地分析MySQL索引设计背后的数据结构和算法,从而可以帮你释疑如下问题:

    lyb-geek
  • LinkedList源码详解

    秋白

扫码关注云+社区

领取腾讯云代金券