Python蓝桥杯训练：基本数据结构 [二叉树] 中

一、翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

示例 2：

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

示例 3：

输入：root = []
输出：[]

提示：

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

这道题目要求我们翻转一棵二叉树，可以使用递归的思路来解决问题。对于一个二叉树而言，可以将它的左右子树看作两个独立的小问题，因此可以先将左右子树分别翻转，然后再将整个树进行翻转。

具体实现时，可以编写一个递归函数，对于每一个节点而言，先分别翻转左右子树，然后将左右子树交换即可。如果节点为空，直接返回即可。

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None

        # 递归翻转左右子树
        left = self.invertTree(root.left)
        right = self.invertTree(root.right)

        # 交换左右子树
        root.left = right
        root.right = left

        return root

上面算法我们使用的遍历顺序是后序遍历，使用前序遍历也可以解决，该算法的时间复杂度为 $O(n)$，其中 $n$ 是二叉树的节点个数，因为每个节点都会被访问一次。空间复杂度为 $O(n)$，因为递归函数会使用系统栈，最坏情况下系统栈的深度等于二叉树的高度，即为 $O(n)$。

二、对称二叉树

给你一个二叉树的根节点 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

**进阶：**你可以运用递归和迭代两种方法解决这个问题吗？

首先，可以通过递归的方法来判断一棵二叉树是否是镜像对称的。对于一棵二叉树而言，如果它是镜像对称的，那么它的左右子树也是镜像对称的。因此，可以编写一个递归函数来判断左右子树是否镜像对称，然后判断根节点的左右子树是否镜像对称即可。

具体实现时，可以编写一个递归函数 isMirror，该函数接受两个参数 left 和 right，分别表示两棵子树。如果两棵子树均为空，返回 True；如果其中一棵子树为空，返回 False；如果两棵子树的根节点的值不相等，返回 False；否则，递归判断两棵子树的左右子树是否镜像对称。

class Solution(object):
    def isSymmetric(self, root):
        # 如果二叉树为空，则直接返回 True
        if not root:
            return True
        # 如果二叉树不为空，则递归判断其左右子树是否镜像对称
        return self.isMirror(root.left, root.right)
    
    def isMirror(self, left, right):
        # 如果两棵二叉树均为空，则返回 True
        if not left and not right:
            return True
        # 如果其中一棵二叉树为空，则返回 False
        if not left or not right:
            return False
        # 如果两棵二叉树的根节点的值不相等，则返回 False
        if left.val != right.val:
            return False
        # 递归判断两棵二叉树的左右子树是否镜像对称
        return self.isMirror(left.left, right.right) and self.isMirror(left.right, right.left)

三、二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：

给定二叉树 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。

题目要求找出二叉树的最大深度，因此可以通过深度优先搜索的方式，而且推荐使用后序遍历来遍历二叉树，记录每个节点的深度，然后返回最大深度即可。

具体实现时，可以编写一个递归函数 maxDepth，该函数接受一个参数 node，表示当前节点。如果当前节点为空，则返回 0；否则，分别递归遍历当前节点的左右子树，返回左右子树深度的较大值加上 1，即为当前节点的深度。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def maxDepth(self, root):
        # 如果二叉树为空，则返回 0
        if not root:
            return 0
        # 分别递归遍历当前节点的左右子树
        left_depth = self.maxDepth(root.left)
        right_depth = self.maxDepth(root.right)
        # 返回左右子树深度的较大值加上 1，即为当前节点的深度
        return max(left_depth, right_depth) + 1

四、二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

**说明：**叶子节点是指没有子节点的节点。

示例 1：

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

示例 2：

输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

提示：

• 树中节点数的范围在 [0, 105] 内
• -1000 <= Node.val <= 1000

题目要求找出二叉树的最小深度，因此我妈可以通过深度优先搜索的方式来遍历二叉树，记录每个节点的深度，然后返回最小深度即可。

具体实现时，可以编写一个递归函数 minDepth，该函数接受一个参数 node，表示当前节点。如果当前节点为空，则返回 0；否则，分别递归遍历当前节点的左右子树，如果当前节点有左右子树，则返回左右子树深度的较小值加上 1，否则返回左右子树深度的较大值加上 1，即为当前节点的深度。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def minDepth(self, root):
        # 如果二叉树为空，则返回 0
        if not root:
            return 0
        # 分别递归遍历当前节点的左右子树
        left_depth = self.minDepth(root.left)
        right_depth = self.minDepth(root.right)
        if not root.left or not root.right:
            # 如果当前节点只有一个子节点，则返回另一个子树的深度加上 1
            return left_depth + right_depth + 1
        else:
            # 如果当前节点有左右子树，则返回左右子树深度的较小值加上 1
            return min(left_depth, right_depth) + 1

这里需要注意的是，在计算当前节点只有一个子节点的情况时，我们需要将其另一个子树的深度加上 1，因为当前节点不是叶子节点，而是只有一个子节点的非叶子节点。

五、完全二叉树的节点个数

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

示例 1：

输入：root = [1,2,3,4,5,6]
输出：6

示例 2：

输入：root = []
输出：0

示例 3：

输入：root = [1]
输出：1

提示：

• 树中节点的数目范围是[0, 5 * 104]
• 0 <= Node.val <= 5 * 104
• 题目数据保证输入的树是 完全二叉树

**进阶：**遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？

在这里我们可以直接当作普通二叉树来处理，也就是之前练习的层序遍历，直接使用那个模板，记录遍历的节点数量就可以了。

在这里我们主要来着重利用完全二叉树的性质来解决问题，由于完全二叉树的特殊性质，我们可以先分别求出左子树和右子树的高度，然后根据它们的高度分情况讨论。

• 如果左右子树的高度相同，说明左子树是一棵满二叉树，右子树是一棵完全二叉树，那么左子树的节点个数可以直接计算，右子树的节点个数可以递归地求解。
• 如果左右子树的高度不同，说明右子树是一棵满二叉树，左子树是一棵完全二叉树，那么右子树的节点个数可以直接计算，左子树的节点个数可以递归地求解。

最终，根据上述讨论的结果，我们可以递归地求解出完全二叉树的节点个数。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def countNodes(self, root):
        if not root:
            return 0
        
        # 分别求出左子树和右子树的高度
        left_height = self.get_height(root.left)
        right_height = self.get_height(root.right)
        
        # 如果左右子树的高度相同，说明左子树是一棵满二叉树，右子树是一棵完全二叉树
        if left_height == right_height:
            # 左子树的节点个数可以直接计算
            return (1 << left_height) + self.countNodes(root.right)
        # 如果左右子树的高度不同，说明右子树是一棵满二叉树，左子树是一棵完全二叉树
        else:
            # 右子树的节点个数可以直接计算
            return (1 << right_height) + self.countNodes(root.left)
        
    def get_height(self, node):
        height = 0
        while node:
            height += 1
            node = node.left
        return height

我们也可以换一个实现思路，首先判断二叉树是否为空，若为空则节点个数为0，直接返回；否则，记录左子树和右子树的根节点，同时记录左子树和右子树的深度，初始值都为0。

接着，通过循环，不断地遍历左子树和右子树，直到无法遍历，统计出左子树和右子树的深度。

如果左子树的深度等于右子树的深度，说明左子树是满二叉树，右子树是完全二叉树，此时可以利用满二叉树的节点数公式计算出总节点数，即 $2^{leftDepth+1}-1$，其中 $leftDepth$ 表示左子树的深度。

如果左子树的深度不等于右子树的深度，说明左子树是完全二叉树，右子树是满二叉树，此时可以递归计算左子树和右子树的节点个数，并将它们加起来再加上根节点，即可得到总节点数。

最终返回计算出的节点数即可。

class Solution:
    def countNodes(self, root) -> int:
        if not root:
            return 0
        left = root.left
        right = root.right
        leftDepth = 0 #这里初始为0是有目的的，为了下面求指数方便
        rightDepth = 0
        while left: #求左子树深度
            left = left.left
            leftDepth += 1
        while right: #求右子树深度
            right = right.right
            rightDepth += 1
        if leftDepth == rightDepth:
            return (2 << leftDepth) - 1 #注意(2<<1) 相当于2^2，所以leftDepth初始为0
        return self.countNodes(root.left) + self.countNodes(root.right) + 1

六、平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

示例 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] 内
• -104 <= Node.val <= 104

首先我们需要思考的是对于一棵二叉树，如果它是一棵空树，则它是平衡二叉树，因为它没有任何节点，高度为0。

接着，我们可以通过递归的方式判断以每个节点为根的子树是否是平衡二叉树。

对于每个节点，我们需要计算它的左子树和右子树的高度，并判断它们的高度差是否大于1，如果大于1，则说明该节点的子树不是平衡二叉树；否则，递归判断它的左子树和右子树是否是平衡二叉树，如果左子树和右子树都是平衡二叉树，则该节点的子树也是平衡二叉树。

最终，如果整个二叉树是平衡二叉树，则返回True，否则返回False。

class Solution:
    def isBalanced(self, root) -> bool:
        # 调用方法 getHeight 来获取二叉树的高度
        if self.getHeight(root) != -1:
            return True
        else:
            return False
        
    def getHeight(self, root):
        # 如果当前节点是空节点，则返回0
        if not root:
            return 0
        # 分别计算当前节点的左右子树的高度
        # 如果左右子树的高度差大于1，则说明该节点不是平衡二叉树，返回-1
        # 否则，返回该节点的高度
        if (leftHeight := self.getHeight(root.left)) == -1:
            return -1
        if (rightHeight := self.getHeight(root.right)) == -1:
            return -1
        if abs(leftHeight - rightHeight) > 1:
            return -1
        else:
            return 1 + max(leftHeight, rightHeight)