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 0 l_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 beautiful if 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 q return 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 True return 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 0 l_height = get_height(node.left) if l_height == -1: return -1 r_height = get_height(node.right) if r_height == -1 or abs(l_height - r_height) > 1: return -1 return max(l_height,r_height) + 1 return 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 traversal def isValidBST(self, root: Optional[TreeNode], left=-inf, right=inf) -> bool: if root is None: return True x = root.val return left < x < right and \ self.isValidBST(root.left,left,x) and \ self.isValidBST(root.right,x,right) # Inorder traversal pre = -inf def isValidBST(self, root: Optional[TreeNode]) -> bool: if root is None: return True if not self.isValidBST(root.left) or \ root.val <= self.pre: return False self.pre = root.val return self.isValidBST(root.right) """ # Postorder traversal def isValidBST(self, root: Optional[TreeNode]) -> bool: def dfs(node:Optional[TreeNode]) -> tuple: if node is None: return inf, -inf l_min, l_max = dfs(node.left) r_min, r_max = dfs(node.right) x = node.val if x <= l_max or x >= r_min: return -inf, inf return min(l_min,x), max(r_max,x) return dfs(root)[0] != -inf