遞歸

遞歸三部曲：

• 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)