力扣156题最全解法：如何上下翻转二叉树（递归与迭代方法详解，附图解）

给定的二叉树：
    1
   / \
  2   3
 / \
4   5
翻转后的二叉树：
    4
   / \
  5   2
       / \
      3   1

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def upsideDownBinaryTree(root: TreeNode) -> TreeNode:
    if not root or not root.left:
        return root
    new_root = upsideDownBinaryTree(root.left)
    root.left.left = root.right
    root.left.right = root
    root.left = None
    root.right = None
    return new_root
# 测试案例
def printTree(root: TreeNode):
    if root:
        print(root.val, end=' ')
        printTree(root.left)
        printTree(root.right)
# 构建示例二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
# 翻转二叉树
new_root = upsideDownBinaryTree(root)
printTree(new_root)  # 输出: 4 5 2 3 1

初始二叉树：
    1
   / \
  2   3
 / \
4   5
递归翻转步骤：
1. 处理节点 1：
   1
  / \
 2   3
/ \
4   5
2. 处理节点 2：
    2
   / \
  4   5
3. 处理节点 4：
4 为空，递归返回
4. 节点 2 的新根为 4：
    4
   / \
  5   2
       / \
      3   1

def upsideDownBinaryTreeIterative(root: TreeNode) -> TreeNode:
    curr = root
    prev = None
    next = None
    temp = None
    while curr:
        next = curr.left
        curr.left = temp
        temp = curr.right
        curr.right = prev
        prev = curr
        curr = next
    return prev
# 测试案例
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
new_root = upsideDownBinaryTreeIterative(root)
printTree(new_root)  # 输出: 4 5 2 3 1

初始二叉树：
    1
   / \
  2   3
 / \
4   5
迭代翻转步骤：
1. curr = 1, prev = None
2. next = 2, curr.left = None, temp = 3, curr.right = None
3. prev = 1, curr = 2
    1
     \
      3
4. next = 4, curr.left = 3, temp = 5, curr.right = 1
5. prev = 2, curr = 4
    2
   / \
  5   1
       \
        3
6. next = None, curr.left = 5, temp = None, curr.right = 2
7. prev = 4, curr = None
    4
   / \
  5   2
       / \
      3   1

1
   / \
  2   3
 / \
4   5

4
   / \
  5   2
       / \
      3   1

1
     / 
    2
   /
  3

3
 / \
2   1