【LeetCode数据结构06】树Tree

ForHHeart / 2023-05-13 / 原文

二叉树的遍历方式

深度优先搜索DFS：前中后序遍历

144. 二叉树的前序遍历
145. 二叉树的后序遍历
94. 二叉树的中序遍历

广度优先搜索BFS：层序遍历

102. 二叉树的层序遍历
107. 二叉树的层次遍历II
199. 二叉树的右视图
637. 二叉树的层平均值
429. N叉树的层序遍历
515. 在每个树行中找最大值
116. 填充每个节点的下一个右侧节点指针
117. 填充每个节点的下一个右侧节点指针II
104. 二叉树的最大深度
111. 二叉树的最小深度

求二叉树的属性

101. 对称二叉树
104. 二叉树的最大深度
111. 二叉树的最小深度
222. 完全二叉树的节点个数
110. 平衡二叉树
257. 二叉树的所有路径
404. 左叶子之和
513. 找树左下角的值
112. 路径总和

二叉树的修改与构造

226. 翻转二叉树
106. 从中序与后序遍历序列构造二叉树
105. 从前序与中序遍历序列构造二叉树
654. 最大二叉树
617. 合并二叉树

求二叉搜索树的属性

700. 二叉搜索树中的搜索
98. 验证二叉搜索树
530.二叉搜索树的最小绝对差
501.二叉搜索树中的众数
538.把二叉搜索树转换为累加树

二叉树公共祖先问题

236. 二叉树的最近公共祖先
235. 二叉搜索树的最近公共祖先

二叉搜索树的修改与构造

701. 二叉搜索树中的插入操作
450. 删除二叉搜索树中的节点
669. 修剪二叉搜索树
108. 将有序数组转换为二叉搜索树

Solutions

102. 二叉树的层序遍历

力扣题目链接

思路

代码

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        "二叉树层序遍历之迭代法"
        # 检查根节点是否为空：若为空，返回[]
        if root == None:
            return []
        
        # 从模块collections中导入deque
        from collections import deque

        # 初始化
        q = deque([root]) # 将根节点存入队列
        results = [] # 结果数组

        # 开始迭代
        # 终止条件：队列为空
        while q:
            size = len(q) # 获取长度，控制每一层的弹出数目
            result = [] # 当前层的结果数组，每一层初始化归零
            for _ in range(size):
                cur = q.popleft() # deque.popleft()：移除第一个元素并返回它的值
                result.append(cur.val) # 存入当前层的结果数组

                # 每次当前节点弹出队列后，将其左右孩子保存至队列
                # 由于获取了size，不需要考虑当前层会弹出孩子的故障
                if cur.left:
                    q.append(cur.left)
                if cur.right:
                    q.append(cur.right)
            # 将当前层存入结果数组
            # 使用append保留了[]，可以做到实现二维数组。(区分append和extend)
            results.append(result)
        return results

107. 二叉树的层次遍历II

力扣题目链接

思路

对上题的结果进行倒序处理

	# 返回结果
        return results[::-1]

代码

class Solution:
    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
        "二叉树层序遍历之迭代法"
        # 检查根节点是否为空：若为空，返回[]
        if root == None:
            return []
        
        # 从模块collections中导入deque
        from collections import deque

        # 初始化
        q = deque([root]) # 将根节点存入队列
        results = [] # 结果数组

        # 开始迭代
        # 终止条件：队列为空
        while q:
            size = len(q) # 获取长度，控制每一层的弹出数目
            result = [] # 当前层的结果数组，每一层初始化归零
            for _ in range(size):
                cur = q.popleft() # deque.popleft()：移除第一个元素并返回它的值
                result.append(cur.val) # 存入当前层的结果数组

                # 每次当前节点弹出队列后，将其左右孩子保存至队列
                # 由于获取了size，不需要考虑当前层会弹出孩子的故障
                if cur.left:
                    q.append(cur.left)
                if cur.right:
                    q.append(cur.right)
            # 将当前层存入结果数组
            # 使用append保留了[]，可以做到实现二维数组。(区分append和extend)
            results.append(result)
	# 返回结果
        return results[::-1]

199. 二叉树的右视图

力扣题目链接

思路

代码

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        # 检查根节点是否为空：若为空，返回[]
        if root == None:
            return []
        
        # 从模块collections中导入deque
        from collections import deque

        # 初始化
        queue = deque([root]) # 将根节点存入队列
        result = [] # 结果数组

        # 开始遍历
        # 终止条件：队列为空
        while queue:
            size = len(queue) # 获取长度，控制每一层的弹出数目
            cur = queue[-1] # 取当前层的最后一个元素
            result.append(cur.val)
            for _ in range(size):
                cur = queue.popleft() # 弹出当前层的第一个元素并返回它的值
                # 每次当前节点弹出队列后，将其左右孩子保存至队列
                # 由于获取了size，不需要考虑当前层会弹出孩子的故障
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
        # 返回结果
        return result