解题思路
完美二叉树的叶子层是满的，所以，树的大小就是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)
效果图
