翻转二叉树

1、题目

图1

2、题解

递归

根据二叉镜像树的定义，考虑\(DFS\)递归遍历二叉树。

算法流程：

• 终止条件：当节点root为空时，则返回None
• 递归：
  • 初始化节点tmp，暂存root的左子节点
  • 开始递归右子节点，并将返回值作为root的左子节点
  • 开始递归左子节点，并将返回值作为root的右子节点
• 返回：当前节点root

# 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]:
        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

# 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]:
        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