翻转二叉树
1、题目
图1
2、题解
递归
根据二叉镜像树的定义,考虑\(DFS\)递归遍历二叉树。
算法流程:
- 终止条件:当节点root为空时,则返回None
- 递归:
- 初始化节点tmp,暂存root的左子节点
- 开始递归右子节点,并将返回值作为root的左子节点
- 开始递归左子节点,并将返回值作为root的右子节点
- 返回:当前节点root
1 2 3 4 5 6 7 8 9 10 11 12 13 14
|
class Solution: def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: if not root: return tmp = root.left root.left = self.invertTree(root.right) root.right = self.invertTree(tmp) return root
|
辅助栈
算法流程:
- 当root为空时,直接返回None
- 初始化栈,加入根节点root
- 当栈为空时结束。出栈的节点记为node,将node左和右子节点入栈,交换node的左右子节点
- 返回根节点root
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
|
class Solution: def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: if not root: return root stack = [root] while stack: node = stack.pop() if node.left: stack.append(node.left) if node.right: stack.append(node.right)
node.left,node.right = node.right, node.left return root
|