问题LeetCode给你一棵完美的二叉树，其中所有叶子都在同一层，每个父母都有两个孩子。二叉树有如下定义：structNode{intval;节点*左；节点*右；Node*next;}填充每个next指针以指向其下一个右节点。如果没有下一个右节点，下一个指针应该设置为NULL。最初，所有下一个指针都设置为NULL。跟进：你可能只使用常量额外空间。递归方法很好，你可以假设隐式堆栈空间不算作此问题的额外空间。示例1：输入：root=[1,2,3,4,5,6,7]输出：[1,#,2,3,#,4,5,6,7,#]说明：给定上面的完美二叉树（图A），你的函数应该填充每个下一个指针指向它的下一个右节点，就像图B中一样。序列化输出按级别顺序由下一个连接指针，“#”表示每个指针的结尾等级。问题给定一棵完美二叉树，它的所有叶子节点都在同一层，每个父节点有两个子节点。二叉树定义如下：structNode{intval;节点*左；节点*右；Node*next;}填充它的每一个next指针，使这个指针指向它的下一个右节点。如果找不到下一个正确的节点，则将next指针设置为NULL。最初，所有下一个指针都设置为NULL。高级：您只能使用恒定数量的额外空间。用递归解决问题也符合要求。本题中递归程序占用的栈空间不算额外的空间复杂度。示例：输入：root=[1,2,3,4,5,6,7]输出：[1,#,2,3,#,4,5,6,7,#]解释：给定一棵二叉树如图A所示，你的函数应该填充它的每一个next指针指向它的下一个右节点，如图B所示。序列化输出是按层顺序遍历的，同一层的节点通过next指针连接,'#'标记每一层的结束。提示：树的节点数小于4096-1000<=node.val<=1000，思路是递归构造一个辅助函数连接每一层节点，连接每两个相邻节点。Python3代码"""#Node.class节点的定义：def__init__(self,val:int=0,left:'Node'=None,right:'Node'=None,next:'Node'=None):self.val=valself.left=leftself.right=rightself.next=next"""class解决方案：defconnect(self,root:'Node')->'Node':ifnotroot:returnNone#连接每两个相邻节点defconnectTwoNode(node1:'Node',node2:'Node'):ifnotnode1ornotnode2:returnnode1.next=node2#连接同一父节点的两个子节点connectTwoNode(node1.left,node1.right)connectTwoNode(node2.left,node2.right)#链接不同父节点的两个子节点connectTwoNode(node1.right,node2.left)connectTwoNode(root.left,root.right)returnrootGocode/***节点的定义。*typeNodestruct{*Valint*Left*Node*Right*Node*Next*Node*}*///设置每个连接两个相邻节点funcconnectTwoNode(node1*Node,node2*Node){ifnode1==nil&&node2==nil{return}node1.Next=node2//连接同一父节点的两个子节点connectTwoNode(node1.Left,node1.Right)connectTwoNode(node2.Left,node2.Right)//链接不同父节点的两个子节点connectTwoNode(node1.Right,node2.Left)}funcconnect(root*Node)*Node{ifroot==nil{returnnil}connectTwoNode(root.Left,root.Right)returnroot}GitHublinkPythonGo
