免费建站网站有哪些,网站收录最好的方法,小公司做网站需要,网上超市怎么做题目#xff1a;
给定二叉树的根节点root,请将它展开为一个单链表#xff1a;
展开后的单链表应该使用同样的TreeNode,其中right子指针指向链表中的下一个节点#xff0c;而左子指针始终为空
展开后的单链表应该与二叉树先序遍历顺序相同 方法一#xff1a;二叉树的前序…题目
给定二叉树的根节点root,请将它展开为一个单链表
展开后的单链表应该使用同样的TreeNode,其中right子指针指向链表中的下一个节点而左子指针始终为空
展开后的单链表应该与二叉树先序遍历顺序相同 方法一二叉树的前序遍历
将二叉树展开为单链表之后单链表中的节点顺序即为二叉树的前序遍历访问各节点的顺序。因此可以对二叉树进行前序遍历获得各节点被访问到的顺序。由于将二叉树展开为链表之后会破坏二叉树的结构因此在前序遍历结束之后更新每个节点的左右子节点的信息将二叉树展开为单链表。
通过递归实现前序遍历
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution(object):def flatten(self, root)::type root: Optional[TreeNode]:rtype: None Do not return anything, modify root in-place instead.preorderList[]#创建一个空列表,用于存储二叉树的所有节点def preorderTraversal(root):#递归函数用于对树进行前序遍历if root: #前序遍历的顺序是根 - 左 - 右。preorderList.append(root)preorderTraversal(root.left)preorderTraversal(root.right)preorderTraversal(root)sizelen(preorderList)#二叉树的节点总数for i in range(1,size): #从第二个节点开始直到最后一个节点。因为链表的第一个节点已经由根节点 root 来表示prev,currpreorderList[i-1],preorderList[i]#取当前节点 curr 和前一个节点 prevprev.leftNone#将 prev 节点的左指针设置为 Noneprev.rightcurr #将 prev 节点的右指针指向 curr
通过迭代的方式实现前序遍历
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution(object):def flatten(self, root)::type root: Optional[TreeNode]:rtype: None Do not return anything, modify root in-place instead.preorderList [] # 初始化一个空列表用于存储二叉树的节点stack [] # 初始化一个空栈用于存储遍历过程中暂时访问的节点node root# 前序遍历二叉树while node or stack:while node:preorderList.append(node) # 将当前节点添加到列表中stack.append(node) # 将当前节点添加到栈中node node.left # 继续遍历左子树node stack.pop() # 当左子树遍历结束时从栈中弹出一个节点这个节点是待访问的右子节点即上一个节点的右子树node node.right # 继续访问右子树# 构建链表右子树按前序遍历顺序连接size len(preorderList)for i in range(1, size): # 从第二个节点开始因为第一个节点已经是链表的头节点prev, curr preorderList[i - 1], preorderList[i]prev.left None # 清空左子树prev.right curr # 将前一个节点的右指针指向当前节点
时间复杂度O(n)其中 n 是二叉树的节点数。前序遍历的时间复杂度是 O(n)前序遍历之后需要对每个节点更新左右子节点的信息时间复杂度也是 O(n)。
空间复杂度O(n)其中 n 是二叉树的节点数。空间复杂度取决于栈递归调用栈或者迭代中显性使用的栈和存储前序遍历结果的列表的大小栈内的元素个数不会超过 n前序遍历列表中的元素个数是 n 方法三寻找前驱节点
前序遍历访问各节点的顺序是根节点、左子树、右子树。如果一个节点的左子节点为空则该节点不需要进行展开操作。。如果一个节点的左子节点不为空则该节点的左子树中的最后一个节点被访问之后该节点的右子节点被访问。该节点的左子树中最后一个被访问的节点是左子树中的最右边的节点也是该节点的前驱节点。因此问题转化成寻找当前节点的前驱节点。
对于当前节点如果其左子节点不为空则在其左子树中找到最右边的节点作为前驱节点,将当前节点的右子节点赋给前驱节点的右子节点然后将当前节点的左子节点赋给当前节点的右子节点并将当前节点的左子节点设为空。对当前节点处理结束后继续处理链表中的下一个节点直到所有节点都处理结束。 # Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution(object):def flatten(self, root)::type root: Optional[TreeNode]:rtype: None Do not return anything, modify root in-place instead.currrootwhile curr:if curr.left:predecessornxtcurr.left#用来找到左子树中最右的节点while predecessor.right:#找到左子树中的最右节点predecessorpredecessor.right #向右移动寻找最右边的节点predecessor.rightcurr.right#找到左子树中的最右节点后,将当前节点的右子树连接到左子树的最右节点上curr.leftNone #当前节点的左子树被置为curr.rightnxt#将当前节点的右指针指向左子树的根节点currcurr.right #使curr移动到下一个节点即当前右子树的第一个节点继续遍历
时间复杂度O(n)其中 n 是二叉树的节点数。展开为单链表的过程中需要对每个节点访问一次在寻找前驱节点的过程中每个节点最多被额外访问一次
空间复杂度O(1)
源自力扣官方题解
