力扣每日一题：226、111、112 二叉树三连发！
2021-06-11 本文已影响0人
清风Python
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
欢迎关注我的公众号: 清风Python，带你每日学习Python算法刷题的同时，了解更多python小知识。
我的个人博客：https://qingfengpython.cn
