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

❤️❤️❤️ 欢迎来到我的博客。希望您能在这里找到既有价值又有趣的内容，和我一起探索、学习和成长。欢迎评论区畅所欲言、享受知识的乐趣！

• 推荐：数据分析螺丝钉的首页 格物致知 终身学习 期待您的关注
  

• 导航：

  • LeetCode解锁1000题: 打怪升级之旅：每题都包括3-5种算法，以及详细的代码实现，刷题面试跳槽必备
  • 漫画版算法详解：通过漫画的形式和动态GIF图片把复杂的算法每一步进行详细可视解读，看一遍就掌握
  • python源码解读：解读python的源代码与调用关系，快速提升代码质量
  • python数据分析可视化：企业实战案例：企业级数据分析案例与可视化，提升数据分析思维和可视化能力
  • 程序员必备的数学知识与应用：全面详细的介绍了工程师都必备的数学知识

期待与您一起探索技术、持续学习、一步步打怪升级 欢迎订阅本专栏❤️❤️

在本篇文章中，我们将详细解读力扣第156题“上下翻转二叉树”。通过学习本篇文章，读者将掌握如何使用递归和迭代的方法来解决这一问题。每种方法都将配以详细的解释和图解，以便于理解。

问题描述

力扣第156题“上下翻转二叉树”描述如下：

给定一个二叉树，将其上下翻转使得原来的右子节点变成新的根节点，并且所有的左子节点依次变成新的右子节点，直到原来的左子节点成为新的叶节点。要求返回新的根节点。

示例：

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

翻转后的二叉树：
    4
   / \
  5   2
       / \
      3   1
1
2
3
4
5
6
7
8
9
10
11
12
13

解题思路

1. 初步分析：

   • 翻转后的树结构较复杂，需要重新定义节点的左右子树。
   • 可以使用递归和迭代的方法实现树的翻转。

2. 多种解法：

   • 递归法：利用递归函数来实现树的翻转。
   • 迭代法：利用栈或队列来实现树的翻转。

递归法

解法思路

递归法通过递归调用函数来处理每个节点，并将当前节点的左子节点变成新的右子节点，右子节点变成新的根节点。

步骤

1. 如果当前节点为空或当前节点的左子节点为空，直接返回当前节点。
2. 递归处理当前节点的左子节点，得到新的根节点。
3. 将当前节点的左子节点的左子节点指向当前节点的右子节点。
4. 将当前节点的左子节点的右子节点指向当前节点。
5. 将当前节点的左子节点和右子节点置为空。
6. 返回新的根节点。

代码实现

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
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

图解

初始二叉树：
    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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

迭代法

解法思路

迭代法通过栈或队列来模拟递归过程，逐步处理每个节点，实现树的翻转。

步骤

1. 初始化当前节点 curr 为根节点 root，prev 为 None，next 为 None，temp 为 None。
2. 迭代处理每个节点：
   • 将 next 指向当前节点的左子节点。
   • 将当前节点的左子节点指向 temp。
   • 将 temp 指向当前节点的右子节点。
   • 将当前节点的右子节点指向 prev。
   • 更新 prev 为当前节点，curr 为 next。
3. 返回 prev 作为新的根节点。

代码实现

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
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

图解

初始二叉树：
    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
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

复杂度分析

• 递归法：

  • 时间复杂度：O(N)，其中 N 是树中节点的数量。每个节点只访问一次。
  • 空间复杂度：O(N)，最坏情况下（树呈链状），递归栈的深度为 N。

• 迭代法：

  • 时间复杂度：O(N)，其中 N 是树中节点的数量。每个节点只访问一次。
  • 空间复杂度：O(1)，只使用了常数空间来存储临时变量。

测试案例分析

1. 测试案例 1：

   • 输入：

         1
        / \
       2   3
      / \
     4   5
     1
     2
     3
     4
     5

   • 输出：

         4
        / \
       5   2
            / \
           3   1
     1
     2
     3
     4
     5

   • 解释：通过递归或迭代方法可以验证树的正确翻转。

2. 测试案例 2：

   • 输入：

      1
     / 
    2
   /
  3
1
2
3
4
5

• 输出：

    3
   / \
  2   1
  1
  2
  3

• 解释：处理单链的树，确保翻转正确。

总结

本文详细解读了力扣第156题“上下翻转二叉树”，通过递归法和迭代法两种不同的解法，帮助读者深入理解如何高效地实现树的翻转。希望读者通过本文的学习，能够在力扣刷题的过程中更加得心应手。

参考资料

• 《算法导论》—— Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
• 力扣官方题解

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Monodyee/article/detail/666946