2025-2-18-4.7 二叉树（基础题）

文章目录

4.7 二叉树（基础题）
- 104. 二叉树的最大深度
- 100. 相同的树
- 101. 对称二叉树
- 110. 平衡二叉树
- 199. 二叉树的右视图（树的深度拓展题）
- 98. 验证二叉搜索树

4.7 二叉树（基础题）

二叉树了，很有趣的数据结构。树的深度、相同的树、对称的树、平衡的树、二叉搜索树。

104. 二叉树的最大深度

题目链接

给定一个二叉树 root ，返回其最大深度。
二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：
在这里插入图片描述
输入：root = [3,9,20,null,null,15,7]
输出：3

示例 2：
输入：root = [1,null,2]
输出：2

提示：

树中节点的数量在 [0, 10^4] 区间内。
-100 <= Node.val <= 100

# 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 maxDepth(self, root: Optional[TreeNode]) -> int:"""时间复杂度：O(n)，其中 n 为二叉树的节点个数。空间复杂度：O(n)。最坏情况下，二叉树退化成一条链，递归需要 O(n) 的栈空间。"""if root is None:return 0l_depth = self.maxDepth(root.left)r_depth = self.maxDepth(root.right)return max(l_depth,r_depth)+1

100. 相同的树

题目链接

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1：
在这里插入图片描述

输入：p = [1,2,3], q = [1,2,3]
输出：true

示例 2：
在这里插入图片描述

输入：p = [1,2], q = [1,null,2]
输出：false

示例 3：
在这里插入图片描述

输入：p = [1,2,1], q = [1,1,2]
输出：false

提示：

两棵树上的节点数目都在范围 [0, 100] 内
-10^4 <= Node.val <= 10^4

# 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 isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:"""时间复杂度：O(min(n,m))，其中n为p的节点个数，m为q的节点个数空间复杂度：O(min(n,m))"""# This if-condition is very beautifulif p is None or q is None:return p is q# Do not add a space after ths backslash. return p.val == q.val and \self.isSameTree(p.left,q.left) and \self.isSameTree(p.right,q.right)

101. 对称二叉树

题目链接
给你一个二叉树的根节点 root ，检查它是否轴对称。

示例 1：
在这里插入图片描述
输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：
在这里插入图片描述

输入：root = [1,2,2,null,3,null,3]
输出：false

提示：

树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100

# 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:"""时间复杂度：O(n)，其中n为二叉树的节点个数。空间复杂度：O(n)。最坏情况下，二叉树退化成一条链，递归需要O(n)的栈空间。"""def isSameTree(self, p:Optional[TreeNode], q:Optional[TreeNode]) -> bool:if p is None or q is None:return p is qreturn p.val == q.val and \self.isSameTree(p.left,q.right) and \self.isSameTree(p.right,q.left)def isSymmetric(self, root: Optional[TreeNode]) -> bool:if root is None: return Truereturn self.isSameTree(root.left,root.right)

110. 平衡二叉树

题目链接
给定一个二叉树，判断它是否是平衡二叉树。

示例 1：
在这里插入图片描述

输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：
在这里插入图片描述

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

示例 3：

输入：root = []
输出：true

提示：

树中的节点数在范围 [0, 5000] 内
-10^4 <= Node.val <= 10^4

# 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 isBalanced(self, root: Optional[TreeNode]) -> bool:"""时间复杂度：O(n)，其中n为二叉树的节点个数。空间复杂度：O(n)。最坏情况下，二叉树退化成一条链，递归需要O(n)的栈空间。"""def get_height(node):if node is None:return 0l_height = get_height(node.left)if l_height == -1:return -1r_height = get_height(node.right)if r_height == -1 or abs(l_height - r_height) > 1:return -1return max(l_height,r_height) + 1return get_height(root) != -1

199. 二叉树的右视图（树的深度拓展题）

题目链接
给定一个二叉树的根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例 1：
输入：root = [1,2,3,null,5,null,4]
输出：[1,3,4]
解释：
在这里插入图片描述

示例 2：
输入：root = [1,2,3,4,null,null,null,5]
输出：[1,3,4,5]
解释：
在这里插入图片描述

示例 3：
输入：root = [1,null,3]
输出：[1,3]

示例 4：
输入：root = []
输出：[]

提示:

二叉树的节点个数的范围是 [0,100]
-100 <= Node.val <= 100

# 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 rightSideView(self, root: Optional[TreeNode]) -> List[int]:"""时间复杂度：O(n)，其中n是二叉树的节点个数。空间复杂度：O(h)，其中h是二叉树的高度。递归需要O(h)的栈空间。最坏情况下，二叉树退化成一条链，递归需要O(n)的栈空间。"""ans = []def f(node, depth):if node is None:return if depth == len(ans):ans.append(node.val)f(node.right,depth+1)f(node.left,depth+1)f(root,0)return ans

98. 验证二叉搜索树

题目链接
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效二叉搜索树定义如下：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1：
在这里插入图片描述

输入：root = [2,1,3]
输出：true

示例 2：
在这里插入图片描述

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

树中节点数目范围在[1, 10^4] 内
-2^31 <= Node.val <= 2^31 - 1

很有趣的一道题，跟着灵神学习，前序、中序以及后序，三种方法，受益匪浅，这里灵神有句话总结的非常到位，就给搬过来了。 【原题解链接】

前序遍历在某些数据下不需要递归到叶子节点就能返回（比如根节点左儿子的值大于根节点的值，左儿子就不会继续往下递归了），而中序遍历和后序遍历至少要递归到一个叶子节点。从这个角度上来说，前序遍历是最快的。
中序遍历很好地利用了二叉搜索树的性质，使用到的变量最少。
后序遍历的思想是最通用的，即自底向上计算子问题的过程。想要学好动态规划的话，请务必掌握自底向上的思想。

# 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:"""时间复杂度：O(n)，其中n为二叉搜索树的节点个数。空间复杂度：O(n)。# Preorder traversaldef isValidBST(self, root: Optional[TreeNode], left=-inf, right=inf) -> bool:if root is None:return Truex = root.valreturn left < x < right and \self.isValidBST(root.left,left,x) and \self.isValidBST(root.right,x,right)# Inorder traversalpre = -infdef isValidBST(self, root: Optional[TreeNode]) -> bool:if root is None:return Trueif not self.isValidBST(root.left) or \root.val <= self.pre:return Falseself.pre = root.valreturn self.isValidBST(root.right)"""# Postorder traversaldef isValidBST(self, root: Optional[TreeNode]) -> bool:def dfs(node:Optional[TreeNode]) -> tuple:if node is None:return inf, -infl_min, l_max = dfs(node.left)r_min, r_max = dfs(node.right)x = node.valif x <= l_max or x >= r_min:return -inf, infreturn min(l_min,x), max(r_max,x)return dfs(root)[0] != -inf