前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode117:填充每个节点的下一个右侧节点指针 II

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

作者头像
爱写bug
发布2020-02-26 11:20:15
5290
发布2020-02-26 11:20:15
举报
文章被收录于专栏:爱写Bug

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

题目:

给定一个二叉树

Given a binary tree

代码语言:javascript
复制
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

代码语言:javascript
复制
输入: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:

代码语言:javascript
复制
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:

代码语言:javascript
复制
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
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-02-24,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 爱写Bug 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • LeetCode117:填充每个节点的下一个右侧节点指针 II Populating Next Right Pointers in Each Node II
    • 题目:
      • 解题思路:
        • Java:
          • Python:
          领券
          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档