首页 » Python » LeetCode Populating Next Right Pointers in Each Node

LeetCode Populating Next Right Pointers in Each Node

2016-03-15 10:40:11阅读(472)

LeetCode解题之Populating Next Right Pointers in Each Node
原题

为二叉树的节点都添加一个next指针,指向跟它在同一高度的右边的节点,如果右边没有节点,就指向None。

注意点:

  • 最好只用常量的空间
  • 这是一棵完全二叉树

例子:

输入:

         1
       /  \
      2    3
     / \  / \
    4  5  6  7

输出:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL
解题思路

这里采用了思路最清晰的解法,但是用的空间不是常量的。可以看出其实就是把树的每一层都串联起来了,要处理每一层的节点,可以使用广度优先遍历,把每一层的节点暂存在列表中,再把这些节点都连接起来。

AC源码
# Definition for binary tree with next pointer.
class TreeLinkNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        self.next = None


class Solution(object):
    def connect(self, root):
        """
        :type root: TreeLinkNode
        :rtype: nothing
        """
        if not root:
            return
        current_level = [root]
        while current_level:
            next_level = []
            for node in current_level:
                if node.left:
                    next_level.append(node.left)
                if node.right:
                    next_level.append(node.right)
            for i in range(len(next_level) - 1):
                next_level[i].next = next_level[i + 1]
            current_level = next_level


if __name__ == "__main__":
    None

欢迎查看我的Github (https://github.com/gavinfish/LeetCode-Python) 来获得相关源码。

最新发布

CentOS专题

关于本站

5ibc.net旗下博客站精品博文小部分原创、大部分从互联网收集整理。尊重作者版权、传播精品博文,让更多编程爱好者知晓!

小提示

按 Ctrl+D 键,
把本文加入收藏夹