力扣156题最全解法:如何上下翻转二叉树(递归与迭代方法详解,附图解)

简介: 力扣156题最全解法:如何上下翻转二叉树(递归与迭代方法详解,附图解)

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

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

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

问题描述

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

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

示例:

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

解题思路

  1. 初步分析
  • 翻转后的树结构较复杂,需要重新定义节点的左右子树。
  • 可以使用递归和迭代的方法实现树的翻转。
  1. 多种解法
  • 递归法:利用递归函数来实现树的翻转。
  • 迭代法:利用栈或队列来实现树的翻转。

递归法

解法思路

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

步骤
  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
递归翻转步骤:
1. 处理节点 1:
   1
  / \
 2   3
/ \
4   5
2. 处理节点 2:
    2
   / \
  4   5
3. 处理节点 4:
4 为空,递归返回
4. 节点 2 的新根为 4:
    4
   / \
  5   2
       / \
      3   1

迭代法

解法思路

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

步骤
  1. 初始化当前节点 curr 为根节点 rootprevNonenextNonetempNone
  2. 迭代处理每个节点:
  • next 指向当前节点的左子节点。
  • 将当前节点的左子节点指向 temp
  • temp 指向当前节点的右子节点。
  • 将当前节点的右子节点指向 prev
  • 更新 prev 为当前节点,currnext
  1. 返回 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
迭代翻转步骤:
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

复杂度分析

  • 递归法
  • 时间复杂度:O(N),其中 N 是树中节点的数量。每个节点只访问一次。
  • 空间复杂度:O(N),最坏情况下(树呈链状),递归栈的深度为 N。
  • 迭代法
  • 时间复杂度:O(N),其中 N 是树中节点的数量。每个节点只访问一次。
  • 空间复杂度:O(1),只使用了常数空间来存储临时变量。

测试案例分析

  1. 测试案例 1
  • 输入:
1
   / \
  2   3
 / \
4   5
  • 输出:
4
   / \
  5   2
       / \
      3   1
  • 解释:通过递归或迭代方法可以验证树的正确翻转。
  1. 测试案例 2
  • 输入:
1
     / 
    2
   /
  3
  • 输出:
3
 / \
2   1
  • 解释:处理单链的树,确保翻转正确。

总结

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

参考资料

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

🌹🌹如果觉得这篇文对你有帮助的话,记得一键三连关注、赞👍🏻、收藏是对作者最大的鼓励,非常感谢 ❥(^_-)

❤️❤️关注公众号 数据分析螺丝钉 回复 学习资料 领取高价值免费学习资料❥(^_-)

欢迎关注微信公众号 数据分析螺丝钉

相关文章
|
14天前
|
算法
刷算法Leetcode---9(二叉树篇Ⅲ)
刷算法Leetcode---9(二叉树篇Ⅲ)
12 3
|
1月前
|
算法 Python
LeetCode 常用方法
LeetCode 常用方法
|
1月前
|
算法
二刷力扣--二叉树(3)
二刷力扣--二叉树(3)
|
1月前
二刷力扣--二叉树(2)
二刷力扣--二叉树(2)
|
1月前
二刷力扣--二叉树(1)基础、遍历
二刷力扣--二叉树(1)基础、遍历
|
1月前
|
算法
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
|
1月前
|
存储 算法 数据可视化
【模拟面试问答】深入解析力扣164题:最大间距(桶排序与排序方法详解)
【模拟面试问答】深入解析力扣164题:最大间距(桶排序与排序方法详解)
|
1月前
|
SQL 算法 数据挖掘
深入解析力扣183题:从不订购的客户(LEFT JOIN与子查询方法详解)
深入解析力扣183题:从不订购的客户(LEFT JOIN与子查询方法详解)
|
1月前
|
算法 数据挖掘 大数据
深入解析力扣172题:阶乘后的零(计算因子5的方法详解及模拟面试问答)
深入解析力扣172题:阶乘后的零(计算因子5的方法详解及模拟面试问答)
|
1月前
|
存储 算法 数据可视化
深入解析力扣157题:用Read4高效读取N个字符(多种解法与详细图解)
深入解析力扣157题:用Read4高效读取N个字符(多种解法与详细图解)