226. Revert Binary Tree
14 Jul 2024
226. Revert Binary Tree (Easy) 反转二叉树
题干
Given the root of a binary tree, invert the tree, and return its root.
Example 1:
Input: root = [4,2,7,1,3,6,9] Output: [4,7,2,9,6,3,1]
Example 2:
Input: root = [2,1,3] Output: [2,3,1]
Example 3:
Input: root = [] Output: []
Constraints:
- The number of nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
解法
递归解法
核心思想：使用前序或后序遍历来处理。
中序遍历不行的原因是，在左和右子树分别处理完之前，就把中的逻辑（交换左右子树）处理了，相当于左右子树发生了改变，逻辑会比较绕。
递归实现：
- 输入参数：Optional[TreeNode]
- 输出参数：空
- 终止条件：如果传入参数为None，返回
- 单层核心逻辑：按照前序或者后序遍历处理
# 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]: self.invertNode(root) return root def invertNode(self, node: Optional[TreeNode]): if node is None: return # 前序遍历 # 处理`中`，交换左右子树 node.left, node.right = node.right, node.left # 递归处理左子树 self.invertNode(node.left) # 递归处理右子树 self.invertNode(node.right)