元宝 LeetCode 116.填充每个节点的下一个右侧节点指针 Python3实现

LeetCode 116 题要求填充每个节点的“next” 指针使其指向右侧相邻的节点。由于题目给定的是完美二叉树我们可以利用这一特性在 O(1) 额外空间内完成递归解法的栈空间不计入额外空间复杂度。以下提供两种 Python3 实现方式方法一利用已建立的 next 指针迭代O(1) 空间推荐思路从根节点开始把每一层看作一个链表。通过上一层已经连接好的“next” 指针来连接当前层的子节点。“”Definition for a Node.class Node:definit(self, val: int 0, left: ‘Node’ None, right: ‘Node’ None, next: ‘Node’ None):self.val valself.left leftself.right rightself.next next“”class Solution:def connect(self, root: ‘Node’) - ‘Node’:if not root:return None# leftmost 指向每一层的最左节点 leftmost root # 只要当前层不是叶子层即还有下一层 while leftmost.left: # head 用于遍历当前层的节点 head leftmost while head: # 1. 同一个父节点的左孩子 - 右孩子 head.left.next head.right # 2. 不同父节点之间当前节点的右孩子 - 下一个节点的左孩子 if head.next: head.right.next head.next.left # 移动到当前层的下一个节点 head head.next # 进入下一层最左边的节点 leftmost leftmost.left return root核心逻辑“head.left.next head.right”连接同一个父节点下的左右孩子。2.“head.right.next head.next.left”如果“head.next” 存在连接相邻父节点的左右子树。3. 外层“while” 逐层深入内层“while” 横向遍历。方法二递归解法简洁直观递归方法利用函数调用栈隐式地完成了层序遍历代码更简洁。class Solution:def connect(self, root: ‘Node’) - ‘Node’:if not root:return None# 如果有左子树完美二叉树有左必有右 if root.left: # 左孩子指向右孩子 root.left.next root.right # 如果有下一个节点右孩子指向 next 的左孩子 if root.next: root.right.next root.next.left # 递归处理左右子树 self.connect(root.left) self.connect(root.right) return root复杂度分析时间复杂度O(N)每个节点只被访问一次。空间复杂度迭代法O(1)只使用了几个指针变量。递归法O(log N)即树高由递归栈产生符合题目进阶要求。你可以直接将上述任一代码提交到 LeetCode 即可通过。需要我帮你分析某一种写法的执行过程或者扩展到 LeetCode 117普通二叉树 的解法吗