python实现leetcode之116. 填充每个节点的下一个

解题思路

完美二叉树的叶子层是满的，所以，树的大小就是2height+1
第一步 先计算树的大小
第二步 申请同样大小的列表，然后将节点放在列表里，因为是二叉树，所以有堆的性质，父节点在idx/2处，左孩子在idx2,右孩子在idx2+1
第三步 设置next节点，同一层的，比如第三层4，5，6，7，任何连续两个的and都不会是0，相反从第三层到第四层7-8的and就是0
arr_idx & arr_idx+1为0表示到当前层的末梢

116. 填充每个节点的下一个右侧节点指针

代码

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

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root: return root
        arr = [None for _ in range(perfect_btree_size(root))]
        put(root, arr, 1)
        arr_idx = 1
        while arr[arr_idx]:
            if arr_idx & (arr_idx + 1) == 0:
                pass  # arr[arr_idx].next = NULL
            else:
               arr[arr_idx].next = arr[arr_idx + 1]
            arr_idx += 1
        return root


def perfect_btree_size(tree, depth=0):
    if not tree: return 2**depth + 1
    return perfect_btree_size(tree.right, depth+1)


def put(tree, li, idx):
    li[idx] = tree
    if tree.left: put(tree.left, li, idx*2)
    if tree.right: put(tree.right, li, idx*2 + 1)