本文讲的是递归。

循环和递归都是编程中常用的控制流程结构，但它们的执行方式和实现方式有所不同。

• 循环是一种通过重复执行一段代码块来解决问题的技术。循环中的代码块会按照一定的条件和次数执行，直到满足退出条件为止。循环通常使用迭代变量来控制循环的次数，例如for循环和while循环。

• 递归是一种在函数定义中使用函数自身的技术。在递归过程中，函数将问题分解成一个或多个子问题的基本情况，然后递归调用自身来解决这些子问题。递归通常用于解决涉及重复执行相同任务的问题，例如遍历数据结构、计算阶乘、斐波那契数列等。

循环和递归的最大区别在于它们的执行方式和语法结构不同。循环是一个迭代的过程，代码块按照一定的顺序和条件执行，而递归是一个分治的过程，通过将问题递归地分解为更小的子问题来解决。另外，递归调用函数本身，而循环使用循环变量来控制循环次数。

在实际应用中，循环和递归各有优劣，需要根据具体问题和需求选择合适的方法。循环通常比递归更高效，但在某些情况下，递归能够提高代码的可读性和可维护性，例如在处理树、图等数据结构时。

几乎所有可以用递归解决的问题都可以使用循环迭代的方式来解决。

一些程序设计语言甚至不支持递归，因此使用循环是唯一的解决方案。在使用递归时，需要注意递归深度的问题，因为递归的过程会增加函数调用栈的深度，可能导致栈溢出等问题。

在实际编程中，应该根据具体问题和实现需求选择合适的方法。如果递归的实现更加简单和直观，且不会出现栈溢出等问题，那么可以使用递归；如果需要更高效的代码和更少的内存消耗，那么可以使用循环。无论是使用循环还是递归，都应该遵循编程规范和最佳实践，编写高质量的代码。

---

面试经典 150 题

104. 二叉树的最大深度

• 104. 二叉树的最大深度 - 力扣（Leetcode）

• Maximum Depth of Binary Tree - LeetCode

Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

 

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: 3

Example 2:

Input: root = [1,null,2]
Output: 2

 

Constraints:

• The number of nodes in the tree is in the range [0,104][0, 10^4][0,104].

• -100 <= Node.val <= 100

从最简单的题入手看递归。要找整个树最大的深度也就是找到根节结点左子树和根节点右子树的最大深度+1。

我们可以将原问题划分为子问题：

• 原问题：计算整棵树的最大深度

• 子问题：计算左／右子树的最大深度

由于子问题的规模比原问题小不断递下去，总会有个尽头，即递归的边界条件（base case）直接返回它的答案，归。

所以写递归只要划分好子问题，找到边界条件即可。

在函数中，首先判断树是否为空，如果为空，直接返回 0；否则，递归计算左子树和右子树的最大深度，并取其中的较大值，最后加上 1 即为树的最大深度。

这个算法的时间复杂度是 O(n)，其中 n 是树的节点数，因为它需要遍历每个节点一次。 空间复杂度是 O(h)，其中 h 是树的高度，因为递归的深度最大为树的高度。

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        leftDep = self.maxDepth(root.left)
        rightDep = self.maxDepth(root.right)
        return max(leftDep,rightDep) + 1

这段代码实现了计算二叉树最大深度的功能，采用的是递归算法。算法首先判断当前节点是否为空，如果为空，则返回深度为0；否则，分别递归计算左右子树的深度，并将其最大值加1作为当前节点的深度，即maxDep+1，其中maxDep为左右子树深度的最大值。最后，算法返回当前节点的深度。

由于算法需要遍历整个二叉树，因此时间复杂度为O(n)，其中n为节点的数量。由于算法采用递归方式实现，需要维护递归栈，因此空间复杂度为O(h)，其中h为树的高度。

要使用数学归纳法来说明该算法的正确性，需要先确定归纳假设和归纳基础：

归纳假设：对于任意一棵二叉树，假设计算其左右子树的最大深度值都是正确的，即 leftDep = self.maxDepth(root.left) 和 rightDep = self.maxDepth(root.right) 返回的是左右子树的最大深度值。

归纳基础：当二叉树为空树时，其最大深度为0，该情况已在算法中处理。

接下来，需要使用数学归纳法来证明归纳假设在一般情况下成立：

归纳步骤：假设对于所有深度不超过 k−1k-1k−1 的二叉树，其计算左右子树的最大深度值都是正确的，即假设归纳假设在深度不超过 k−1k-1k−1 的情况下成立。现考虑深度为 kkk 的情况，如何计算以该二叉树为根节点的子树的最大深度。

根据归纳假设，我们已经知道了该二叉树的左右子树的最大深度，分别为 leftDep 和 rightDep。则以该二叉树为根节点的子树的最大深度为：

这是因为以该二叉树为根节点的子树的最大深度，等于左右子树最大深度的较大值再加1，因为根节点也要算一层深度。

因此，根据归纳步骤和归纳假设，可以得出结论：对于任意一棵二叉树，计算其左右子树的最大深度值都是正确的。

---

只要代码的边界条件和非边界条件的逻辑写对了，其他的事情交给数学归纳法就好了。

从第一题我们继续往下看，本文设计到的都是不需要传递额外值的递归。

111. 二叉树的最小深度⭐

• Minimum Depth of Binary Tree - LeetCode

• 111. 二叉树的最小深度 - 力扣（Leetcode）

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

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

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

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: 2

Example 2:

Input: root = [2,null,3,null,4,null,5,null,6]
Output: 5

 

Constraints:

• The number of nodes in the tree is in the range [0,105][0, 10^5][0,105].

• -1000 <= Node.val <= 1000

我刚做完最大深度，怎么可能不会做最小深度。不是max变min，有手就行？

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        leftDep = self.minDepth(root.left)
        rightDep = self.minDepth(root.right)
        else:
            return min(leftDep,rightDep)+1

恩。然后就做错了。

这个样例你应该输出5，但是你输出的是1。

因为忽略了叶子节点 这个要求。

root没有左子树，root只有右子树，但是上边的写法是求左右子树的深度然后取最小。

没有左子树意味着左边没叶子节点，所以你往左找是没有意义的，有叶子节点的子树才是有意义的 ，因此没有左子树的时候只去右子树找，反之同理。

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        if not root.left and not root.right:    # 叶子结点
            return 1
        elif not root.left:     # 没左子树，往右找
            return self.minDepth(root.right) + 1
        elif not root.right:    # 没右子树，往左找
            return self.minDepth(root.left) + 1
        else:   # 左右子树都有
            return min(self.minDepth(root.left),self.minDepth(root.right))+1

• 如果二叉树为空，则深度为0，返回0。
• 如果二叉树是叶子节点，则深度为1，返回1。
• 如果只有左子树，那么在左子树上递归计算深度，然后深度+1。
• 如果只有右子树，那么在右子树上递归计算深度，然后深度+1。
• 如果既有左子树又有右子树，则在左子树和右子树中分别递归计算深度，取最小值，然后+1作为深度。

最后返回深度值。

这段代码已经比较简洁，但是可以稍加优化。可以将左右子树为空的情况合并到有左右子树的情况中，使代码更加简洁。具体来说，可以使用三目运算符来判断左右子树是否为空，然后返回左右子树的最小深度加1，如下所示：

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        leftDep = self.minDepth(root.left)
        rightDep = self.minDepth(root.right)
        return (min(leftDep,rightDep) or max(leftDep,rightDep)) + 1

这里使用了 or 和 and 的短路特性来处理当左子树或右子树为空时，避免出现 None。

如果 left_depth 和 right_depth 中有一个为 0（即对应的子树为空），那么 min(left_depth, right_depth) or max(left_depth, right_depth) 就等于不为空的那个子树的深度，而如果两者都不为 0，就返回它们的最小值加 1。

---

226. 翻转二叉树

给你一棵二叉树的根节点 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: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        # 把二叉树两个子树翻转
        root.left,root.right =  root.right,root.left
        # 翻转左子树和右子树
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

这个算法实现了翻转二叉树的功能。算法使用递归的方式，对于每个节点，交换它的左右子节点，然后递归翻转左右子树。最后返回根节点。

由于算法遍历了每个节点一次，因此时间复杂度为O(n)，其中n为二叉树中节点的个数。由于算法使用了递归，因此需要维护递归栈，空间复杂度也为O(n)。

114. 二叉树展开为链表

给你二叉树的根结点 root ，请你将它展开为一个单链表：

• 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
• 展开后的单链表应该与二叉树 先序遍历 顺序相同。

 

示例 1：

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

示例 2：

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

示例 3：

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

 

提示：

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

进阶： 你可以使用原地算法（O(1) 额外空间）展开这棵树吗？

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        if not root:
            return

        r = root.right
        root.right = root.left
        root.left = None
        
        p = root
        while p.right:
            p = p.right
        p.right = r

        self.flatten(root.left)
        self.flatten(root.right)

        return root

这个函数实现了将二叉树展开成链表的功能。具体实现如下：

1. 对于当前节点，首先将其左子树展开成链表，再将右子树展开成链表。
2. 将左子树展开成链表后，原左子树的根节点会变成展开后链表的最后一个节点，因此需要将其指向原来右子树展开后链表的头节点。
3. 对于右子树展开后得到的链表，需要将其连接到左子树展开后的链表后面，即将左子树展开后的最后一个节点的右子节点指向右子树展开后的链表头节点。
4. 将当前节点的左子节点设为None。

该算法的时间复杂度为O(n)，其中n为二叉树的节点个数，因为每个节点都只会被访问一次。由于使用了递归调用栈，空间复杂度为O(h)，其中h为二叉树的高度。

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

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q:
            return True
        elif not p or not q:
            return False
        elif p.val != q.val:
            return False
        else:
            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

该函数实现了判断两个二叉树是否相同的功能。其中，参数p和q分别为待比较的两个二叉树的根节点，函数返回值为布尔类型，表示这两个二叉树是否相同。在函数中，首先判断p和q是否都为空，如果都为空，返回True。如果只有一个为空，返回False。如果p和q都不为空，继续递归比较它们的左右子树是否相同。如果左右子树都相同，返回True，否则返回False。

因为每个节点只会被访问一次，所以时间复杂度为O(n)，其中n为树中节点的个数。因为需要递归调用函数，所以空间复杂度为O(h)，其中h为树的高度，最坏情况下，h等于n，即树退化为链表的情况。

也可以这么写：

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p or not q:
            return p == q
        elif p.val != q.val:
            return False
        else:
            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

或者写成

    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p or not q:
            return p == q
        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

 

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

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        
        def dfs(l,r):
            if not l or not r:
                return l == r 
            return l.val == r.val and dfs(l.left,r.right) and dfs(l.right,r.left)

        return dfs(root.left,root.right) 

这段代码实现了判断一棵二叉树是否是镜像对称的功能。算法使用递归实现，定义了一个辅助函数dfs，其参数为左子树的根节点l和右子树的根节点r。如果左右子树均为空，那么它们显然对称，返回True。如果其中一个为空，另一个不为空，那么它们不对称，返回False。如果左右子树的根节点的值不相等，那么它们不对称，返回False。最后，判断左子树的左孩子和右子树的右孩子是否对称，并判断左子树的右孩子和右子树的左孩子是否对称。如果都对称，返回True，否则返回False。

因为每个节点最多被遍历一次，所以时间复杂度为O(n)，其中n为二叉树节点的个数。递归调用栈的深度最多为二叉树的高度，所以空间复杂度为O(h)，其中h为二叉树的高度。

这代码眼熟不？ 不眼熟可以看这个：

class Solution:
    
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p or not q:
            return p == 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:
        return self.isSameTree(root.left,root.right)

---

再来个练习

110. 平衡二叉树

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

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

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 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

class Solution:
    def height(self, root):
        if not root:
            return 0
        lef = self.height(root.left)
        rig = self.height(root.right)
        if abs(lef - rig) > 1 or lef == -1 or rig == -1:
            return -1
        return max(lef, rig) + 1

    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        return self.height(root) != -1

• height()函数返回以根节点root为根的二叉树的高度。如果root是None，则返回0。否则，递归计算左子树和右子树的高度，并判断它们的高度差是否大于1。如果高度差大于1或者左子树或右子树的高度为-1，则返回-1，表示该二叉树不平衡。否则，返回左子树和右子树高度的最大值加1，即以root为根的二叉树的高度。
• isBalanced()函数返回二叉树是否平衡。如果以root为根的二叉树不平衡，则返回False。否则，返回True。

这段代码的思路是利用递归计算每个节点的左子树和右子树的高度，判断它们的高度差是否大于1，从而判断整棵二叉树是否平衡。如果发现不平衡的子树，可以直接返回-1，不再进行递归，从而提高效率。