当前位置: 首页 > article >正文

力扣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:
                return
            res.append(cur)
            dfs(cur.left)
            dfs(cur.right)
        res = []
        dfs(root)
        for idx, n in enumerate(res):
            if idx == len(res)-1:  
                n.left = None
                n.right = None
            else:
                n.left = None
                n.right = res[idx+1]

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

在这里插入图片描述

  • 思路:
    根据前中后序任意两个可以重建一颗二叉树,只靠前序和后序不是唯一的。
  • 代码:
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if not preorder:  # 空节点
            return None
        left_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 None
        if 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)

http://www.kler.cn/a/580581.html

相关文章:

  • FastAPI 表单参数与文件上传完全指南:从基础到高级实战 [特殊字符]
  • 如何实现创意的角落切割效果:使用 CSS 和 SVG 创建时尚的网页元素
  • NLP常见任务专题介绍(1)-关系抽取(Relation Extraction, RE)任务训练模板
  • TypeError: Cannot convert object to primitive value
  • JavaScript(最后一个元素的索引就是数组的长度减 1)array.length - 1
  • Java 大视界 -- 基于 Java 的大数据实时数据处理框架性能评测与选型建议(121)
  • 请谈谈 TypeScript 中的接口(interface)和类型别名(type alias),它们的区别是什么?
  • Python | 机器学习中最常用的超参数及使用示例
  • Qt常用控件之树形QTreeWidget
  • 如何使用postman来测试接口
  • Synology 部署的 WordPress 無法升級至最新版本時,可以透過以下改良版指南進行排查和解決。
  • 雪藏HsFreezer(游戏冻结工具) v2.21
  • jsonRPC实现前后端分离
  • delphi 正则提取html中的内容
  • listen EACCES: permission denied 0.0.0.0:811
  • Ubuntu 创建systemd服务
  • LeetCode 2380 二进制字符串重新安排顺序需要的时间
  • Docker Compose国内镜像一键部署dify
  • C#常用的循环语句
  • 马斯克:AI游戏前景无限