力扣hot100_二叉树(4)_python版本

一、199. 二叉树的右视图

• 思路：
  直接复用层序遍历的代码，然后取每层的最后一个节点
• 代码：

class Solution:def rightSideView(self, root: Optional[TreeNode]) -> List[int]:'''层序遍历取每层的第一个'''if not root: return []res = []queue = collections.deque()queue.append(root)while queue:tmp_res = []for _ in range(len(queue)):node = queue.popleft()tmp_res.append(node.val)if node.left:queue.append(node.left)if node.right:queue.append(node.right)res.append(tmp_res[-1])  # 只需要修改层序遍历的这里return res

二、114. 二叉树展开为链表

• 思路：
  直接复用先序遍历，然后遍历结果，依次修改结果就行
• 代码：

class Solution:def flatten(self, root: Optional[TreeNode]) -> None:"""Do not return anything, modify root in-place instead.可以先序遍历节点，将节点放到列表中，然后连接上各节点"""def dfs(cur):if not cur:returnres.append(cur)dfs(cur.left)dfs(cur.right)res = []dfs(root)for idx, n in enumerate(res):if idx == len(res)-1:  n.left = Nonen.right = Noneelse:n.left = Nonen.right = res[idx+1]

三、105. 从前序与中序遍历序列构造二叉树

• 思路：
  根据前中后序任意两个可以重建一颗二叉树，只靠前序和后序不是唯一的。
• 代码：

class Solution:def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:if not preorder:  # 空节点return Noneleft_size = inorder.index(preorder[0])  # 左子树的大小left = self.buildTree(preorder[1: 1 + left_size], inorder[:left_size])right = self.buildTree(preorder[1 + left_size:], inorder[1 + left_size:])return TreeNode(preorder[0], left, right)

四、889. 根据前序和后序遍历构造二叉树

• 代码：

class Solution:def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:if not preorder:  # 空节点return Noneif len(preorder) == 1:  # 叶子节点return TreeNode(preorder[0])left_size = postorder.index(preorder[1]) + 1  # 左子树的大小left = self.constructFromPrePost(preorder[1: 1 + left_size], postorder[:left_size])right = self.constructFromPrePost(preorder[1 + left_size:], postorder[left_size: -1])return TreeNode(preorder[0], left, right)