leetcode 每个结点的右指针 python

每个节点的右向指针

给定一个二叉树

struct TreeLinkNode {

  TreeLinkNode *left;

  TreeLinkNode *right;

  TreeLinkNode *next;

}

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

初始状态下，所有 next 指针都被设置为 NULL。

说明:

你只能使用额外常数空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
你可以假设它是一个完美二叉树（即所有叶子节点都在同一层，每个父节点都有两个子节点）。

示例:

给定完美二叉树，

调用你的函数后，该完美二叉树变为：

     1 -> NULL

   /  \

  2 -> 3 -> NULL

 / \  / \

4->5->6->7 -> NULL

leetcode 每个结点的右指针 python

我的想法是把每一层次存起来，然后对每一层次修改每个节点的右侧指针

 # Definition for binary tree with next pointer.

 # class TreeLinkNode:

 #     def __init__(self, x):

 #         self.val = x

 #         self.left = None

 #         self.right = None

 #         self.next = None

 class Solution:

     # @param root, a tree link node

     # @return nothing

     def connect(self, root):

         if root is None:

             return root

         tree = [[root]]

         i = 0

         while i < len(tree):

             cur = tree[i]

             layer = []

             for c in cur:

                 if c.left is not None:

                     layer.append(c.left)

                 if c.right is not None:

                     layer.append(c.right)

             if layer:

                 tree.append(layer)

             i += 1

         for l in tree:

             for i in range(len(l)-1):

                 l[i].next = l[i+1]

秒客网

leetcode 每个结点的右指针 python

相关文章