给定一个二叉树
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
进阶：
- 你只能使用常量级额外空间。
- 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
示例：
输入：root = [1,2,3,4,5,null,7] 输出：[1,#,2,3,#,4,5,7,#] 解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。
提示：
- 树中的节点数小于
6000 -100 <= node.val <= 100
**难度**: Medium
**标签**: 树、 深度优先搜索、
# -*- coding: utf-8 -*-
# @Author : LG
"""
执行用时：60 ms, 在所有 Python3 提交中击败了81.56% 的用户
内存消耗：14.5 MB, 在所有 Python3 提交中击败了54.12% 的用户
解题思路：
先把每层的节点以自左向右的顺序保存，
然后修改next
"""
class Solution:
def connect(self, root: 'Node') -> 'Node':
record = {}
def find(root, h): # 遍历，并保存每层的节点
if root:
if h in record:
record[h].append(root)
else:
record[h] = [root]
find(root.left, h+1) # 自左向右的顺序遍历
find(root.right, h+1)
find(root, 1)
for h, ns in record.items(): # 处理每层的节点
for i in range(len(ns)-1):
ns[i].next = ns[i+1]
ns[-1] = None
return root