欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode116. 填充每个节点的下一个右侧节点指针(O(1)空间)

程序员文章站 2022-05-20 20:09:14
...

1、题目描述

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

LeetCode116. 填充每个节点的下一个右侧节点指针(O(1)空间)

LeetCode116. 填充每个节点的下一个右侧节点指针(O(1)空间)

给定二叉树如图 A 所示,你的函数应该填充它的每个 next 指针,以指向其下一个右侧节点,如图 B 所示。

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

2、代码详解

完美二叉树,即每一层的节点都是满的。

完成后的串联树,其连接的方式有两种:

  • 第一种是这两个串联的节点都有一个共同的父节点,通过父节点就可以将这两个子节点串联起来
  • 第二种是这两个串联的节点的父节点不同,对于这种情况,如果我们能将这一层的上一层串联好。那么可以通过父节点的next找到邻居,完成串联。

LeetCode116. 填充每个节点的下一个右侧节点指针(O(1)空间)LeetCode116. 填充每个节点的下一个右侧节点指针(O(1)空间)

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val=0, left=None, right=None, next=None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution(object):
    def connect(self, root):
        """
        :type root: Node
        :rtype: Node
        """
        if not root:
            return root
        pre = root
        # 循环条件是当前节点的left不为空
        while pre.left:
            tmp = pre
            while tmp:
                tmp.left.next = tmp.right  # 同一父节点的串联,将tmp的左右节点都串联起来
                if tmp.next:  # 上一层已串联好了
                    tmp.right.next = tmp.next.left  # 非同一父节点的串联
                tmp = tmp.next  # 继续右边遍历
            pre = pre.left  # 从下一层的最左边开始遍历
        return root

迭代法2:层序遍历(队列)非O(1)

递归

https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/solution/dong-hua-yan-shi-san-chong-shi-xian-116-tian-chong/