算法训练营第十三天｜226.翻转二叉树、101. 对称二叉树、 104.二叉树的最大深度、111.二叉树的最小深度

递归

递归三部曲：

• 1.确定参数和返回值
• 2.确定终止条件
• 3.确定单层逻辑

226.翻转二叉树

题目

思路与解法

第一想法： 递归，对每个结点进行反转

# 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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:cur = rootif cur:tmp = cur.leftcur.left = cur.rightcur.right = tmpself.invertTree(cur.left)self.invertTree(cur.right)return root

101. 对称二叉树

题目

思路与解法

carl的讲解：

# 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 isSymmetric(self, root: Optional[TreeNode]) -> bool:if not root:return Truedef compare(left, right) -> bool:if not ((left and right) or (not left and not right)):return Falseif not left and not right:return Trueelif left.val != right.val:return Falseif not compare(left.left, right.right):return Falseif not compare(left.right, right.left):return Falsereturn Truereturn compare(root.left, root.right)

104.二叉树的最大深度

题目

思路与解法

第一思路： 可以用层序遍历，记录层数。递归的话就得想想了。不好描述，先写吧。
写了出来，在37/39个示例报超时。

发现超时的原因了，因为 16、17、18行的代码将get_depth(depth, node.left)和get_depth(depth, node.right)各计算了两次。对于树这种递归结构，这是严重的性能问题。
修改方式很简单，获取返回值后再比较就好：

**carl的讲解：**不再显示传递depth参数，因为递归本身隐式计算深度

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

111.二叉树的最小深度

题目

思路与解法

第一想法： 就是简单的改前面的最大深度为最小深度。但是踩坑了，不是这么简单。
**carl的讲解：**因为最小深度的判别要比最大深度复杂。直接将max改成min是不行的，因为会把非叶子节点的值当作最小值返回。因为这个非叶子节点可能离根节点不愿，左边没节点但是右边有节点，这样他就可能得出的depth很小，但是他都不是叶子节点。

# 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: Optional[TreeNode]) -> int:return self.get_depth(root)def get_depth(self, node: Optional[TreeNode]) -> int:if not node:return 0left_depth = self.get_depth(node.left)right_depth = self.get_depth(node.right)if node.left is None and node.right is not None:return right_depth + 1if node.right is None and node.left is not None:return left_depth + 1return 1 + min(left_depth, right_depth)