104、二叉树的深度
难度：简单
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3
/
9 20
/
15 7
返回它的最大深度 3 。
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Solution: # 深度优先搜索 def maxDepth(self, root: Optional[TreeNode]) -> int: if root == None: return 0 leftHeight = self.maxDepth(root.left) rightHeight = self.maxDepth(root.right) return max(leftHeight, rightHeight) + 1 # 广度优先搜索 def maxDepth(self, root: Optional[TreeNode]) -> int: if not root: return 0 queue = [root] res = 0 while queue: size = len(queue) for _ in range(size): curr = queue.pop(0) if curr.left: queue.append(curr.left) if curr.right: queue.append(curr.right) res +=1 return res
112、路径总和
难度：简单
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
示例 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 解释：树中存在两条根节点到叶子节点的路径： (1 --> 2): 和为 3 (1 --> 3): 和为 4 不存在 sum = 5 的根节点到叶子节点的路径。
示例 3： 输入：root = [], targetSum = 0 输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。
# Definition for a binary tree node. class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Solution: def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool: # 递归求解 return self.sum(root, targetSum, 0) def sum(self, root:TreeNode, targetSum:int, currSum:int): if root == None: return False curSum += root.val if root.left == None and root.right == None: return currSum == targetSum else: return self.sum(root.left, targetSum, currSum) or self.sum(root.right, targetSum, currSum) # 广度优先搜索进行遍历 def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool: if not root: return False queue = [root] queue_val = [root.val] while queue: now = queue.pop(0) temp = queue_val.pop(0) if not now.left and not now.right: if temp == targetSum: return True continue if now.left: queue.append(now.left) queue_val.append(now.left.val + temp ) if now.right: queue.append(now.right) queue_val.append(now.right.val + temp) return False
111、二叉树的最小深度
难度：简单
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例 1:
输入：root = [3,9,20,null,null,15,7]
输出：2
示例 2：
输入：root = [2,null,3,null,4,null,5,null,6]
输出：5
# Definition for a binary tree node. class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Solution: # 方法一：深度优先搜索 def minDepth(self, root: TreeNode) -> int: if not root: return 0 if not root.left and not root.right: return 1 min_depth = 10**9 if root.left: min_depth = min(self.minDepth(root.left), min_depth) if root.right: min_depth = min(self.minDepth(root.right), min_depth) return min_depth + 1 # 方法二：广度优先搜索 import collections def minDepth(self, root: TreeNode) -> int: if not root: return 0 que = collections.deque([(root,1)]) while que: node, depth = que.popleft() if not node.left and not node.right: return depth if node.left: que.append((node.left, depth + 1)) if node.right: que.append((node.right, depth + 1)) return 0
108、将有序数组转换为二叉搜索树
难度：简单
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
示例 1：
输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
示例 2：
输入：nums = [1,3]
输出：[3,1]
解释：[1,3] 和 [3,1] 都是高度平衡二叉搜索树。
提示：
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 按 严格递增 顺序排列
# Definition for a binary tree node. class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Solution: # 方法一：中序遍历，总是选择中间位置左边的数字作为根节点 def sortedArrayToBST(self, nums: List[int]) -> TreeNode: def helper(left, right): if left > right: return None mid = (left + right) // 2 root = TreeNode(nums[mid]) root.left = helper(left, mid - 1) root.right = helper(mid + 1, right) return root return helper(0, len(nums) - 1) # 方法二：中序遍历，总是选择中间位置右边的数字作为根节点 def sortedArrayToBST(self, nums: List[int]) -> TreeNode: def helper(left, right): if left >right: return None mid = (left + right + 1) //2 root = TreeNode(nums[mid]) root.left = helper(left, mid - 1) root.right = helper(mid + 1, right) return root return helper(0, len(nums) - 1) # 方法三：中序遍历，选择任意一个中间位置数字作为根节点 class Solution: def sortedArrayToBST(self, nums: List[int]) -> TreeNode: def helper(left, right): if left > right: return None # 选择任意一个中间位置数字作为根节点 mid = (left + right + randint(0, 1)) // 2 root = TreeNode(nums[mid]) root.left = helper(left, mid - 1) root.right = helper(mid + 1, right) return root return helper(0, len(nums) - 1)
173、二叉搜索树迭代器
难度：中等
实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器：
BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。
boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。
int next()将指针向右移动，然后返回指针处的数字。
注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。
你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 的中序遍历中至少存在一个下一个数字。
示例：
输入
[“BSTIterator”, “next”, “next”, “hasNext”, “next”, “hasNext”, “next”, “hasNext”, “next”, “hasNext”]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
输出
[null, 3, 7, true, 9, true, 15, true, 20, false]
解释
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next(); // 返回 3
bSTIterator.next(); // 返回 7
bSTIterator.hasNext(); // 返回 True
bSTIterator.next(); // 返回 9
bSTIterator.hasNext(); // 返回 True
bSTIterator.next(); // 返回 15
bSTIterator.hasNext(); // 返回 True
bSTIterator.next(); // 返回 20
bSTIterator.hasNext(); // 返回 False
提示：
树中节点的数目在范围 [1, 105] 内
0 <= Node.val <= 106
最多调用 105 次 hasNext 和 next 操作
进阶：
你可以设计一个满足下述条件的解决方案吗？next() 和 hasNext() 操作均摊时间复杂度为 O(1) ，并使用 O(h) 内存。其中 h 是树的高度。
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class BSTIterator: def __init__(self, root: TreeNode): self.stack = [] self.in_order(root) def next(self) -> int: node = self.stack.pop() if node.right: self.in_order(node.right) return node.val def in_order(self, node): while node: self.stack.append(node) node = node.left def hasNext(self) -> bool: return len(self.stack) != 0 # Your BSTIterator object will be instantiated and called as such: # obj = BSTIterator(root) # param_1 = obj.next() # param_2 = obj.hasNext()
