36、二叉樹的中序遍歷

給定一個二叉樹的根節點 root ，返回 它的 *中序 遍歷* 。

示例 1：

輸入：root = [1,null,2,3]
輸出：[1,3,2]

示例 2：

輸入：root = []
輸出：[]

示例 3：

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

提示：

• 樹中節點數目在范圍 [0, 100] 內
• -100 <= Node.val <= 100

思路解答：

1、遞歸 左-根-右即可

def inorderTraversal(self, root: Optional[TreeNode]) -> list[int]:def inorder(node,result):if not node:return []inorder(node.left,result)result.append(node.val)inorder(node.right,result)result = []inorder(root,result)return result

37、二叉樹的最大深度

給定一個二叉樹 root ，返回其最大深度。

二叉樹的 最大深度 是指從根節點到最遠葉子節點的最長路徑上的節點數。

示例 1：

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

示例 2：

輸入：root = [1,null,2]
輸出：2

提示：

• 樹中節點的數量在 [0, 104] 區間內。
• -100 <= Node.val <= 100

思路解答：

1、遞歸計算左子樹和右子樹的深度，取兩者中的較大值，并加上1（當前節點的深度）作為樹的深度。

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

38、翻轉二叉樹

給你一棵二叉樹的根節點 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

思路解答：

1、交換每個節點的左右子樹，然后遞歸地對左右子樹進行翻轉

def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:if not root:return None#交換左右子樹root.left, root.right = root.right, root.leftinvertTree(root.left)invertTree(root.right)return root

39、對稱二叉樹

給你一個二叉樹的根節點 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

思路解答：

1、遞歸地比較兩個節點及它們的子樹是否軸對稱 具體就是：遞歸地比較左子樹的左節點與右子樹的右節點，以及左子樹的右節點與右子樹的左節點他們的值是否相同即可

def isSymmetric(self, root: Optional[TreeNode]) -> bool:def isMirror(left, right):if not left and not right:return Trueif not left or not right:return Falsereturn (left.val == right.val) and isMirror(left.left, right.right) and isMirror(left.right, right.left)if not root:return Truereturn isMirror(root.left, root.right)

40、二叉樹的直徑

給你一棵二叉樹的根節點，返回該樹的 直徑 。

二叉樹的 直徑 是指樹中任意兩個節點之間最長路徑的 長度 。這條路徑可能經過也可能不經過根節點 root 。

兩節點之間路徑的 長度 由它們之間邊數表示。

示例 1：

輸入：root = [1,2,3,4,5]
輸出：3
解釋：3 ，取路徑 [4,2,1,3] 或 [5,2,1,3] 的長度。

示例 2：

輸入：root = [1,2]
輸出：1

提示：

• 樹中節點數目在范圍 [1, 104] 內
• -100 <= Node.val <= 100

思路解答：

1、對于每個節點，遞歸地計算左子樹的深度和右子樹的深度。

2、計算每個節點的深度時，計算經過當前節點的路徑長度（左子樹深度 + 右子樹深度），并更新全局變量來記錄最大直徑。

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