226.翻转二叉树
难度：简单
题目：
翻转一棵二叉树。
备注:
这个问题是受到 Max Howell 的 原问题 启发的 ：
谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。
示例：
输入： 4 / \ 2 7 / \ / \ 1 3 6 9 输出： 4 / \ 7 2 / \ / \ 9 6 3 1
分析
只能说这是一套涨自信的题目，主要是这个备注，我已经超过了谷歌90%的人，还学什么？
接着奏乐，接着舞！
解题：
class Solution: def invertTree(self, root): if not root: return root root.left, root.right = root.right, root.left self.invertTree(root.left) self.invertTree(root.right) return root
111.二叉树的最小深度
https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
难度：简单
题目：
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
提示：
- 树中节点数的范围在 [0, 10 ^ 5] 内
- -1000 <= Node.val <= 1000
示例：
网络异常，图片无法展示
|
image
输入：root = [3,9,20,null,null,15,7] 输出：2 示例 2： 输入：root = [2,null,3,null,4,null,5,null,6] 输出：5
分析
计算二叉树的最小深度，那么广度优先的效率是要比深度优先高的。
我们通过队列来逐层遍历二叉树，一旦发现某个树节点既没有左子树和右子树，那么直接返回即可。
解题：
from collections import deque class Solution: def minDepth(self, root: TreeNode) -> int: if not root: return 0 dq,depth = deque([root]), 1 while dq: for i in range(len(dq)): tmp = dq.popleft() if not tmp.left and not tmp.right: return depth if tmp.left: dq.append(tmp.left) if tmp.right: dq.append(tmp.right) depth += 1 return depth
112.路径总和
https://leetcode-cn.com/problems/path-sum/solution/112lu-jing-zong-he-python-di-gui-bfs-shu-lmym/
难度：简单
题目：
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
叶子节点 是指没有子节点的节点。
提示：
- 树中节点的数目在范围 [0, 5000] 内
- -1000 <= Node.val <= 1000
- -1000 <= targetSum <= 1000
示例：
网络异常，图片无法展示
|
示例 1： 输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 输出：true 示例 2： 输入：root = [1,2,3], targetSum = 5 输出：false 示例 3： 输入：root = [1,2], targetSum = 0 输出：false
分析
递归的解题，相信大家第一时间都可以想到。但顺手练练广度优先也是不错的...
解题-递归：
class Solution: def hasPathSum(self, root, targetSum): if not root: return False targetSum -= root.val if not (root.left or root.right) and targetSum == 0: return True return self.hasPathSum(root.left, targetSum) or \ self.hasPathSum(root.right, targetSum)
解题-BFS：
from collections import deque class Solution: def hasPathSum(self, root: TreeNode, targetSum: int) -> bool: if not root: return False queue = deque([[root, targetSum]]) while queue: for i in range(len(queue)): child, num = queue.popleft() num -= child.val if not (child.left or child.right) and num == 0: return True if child.left: queue.append([child.left, num]) if child.right: queue.append([child.right, num]) return False
