❤️❤️❤️ 欢迎来到我的博客。希望您能在这里找到既有价值又有趣的内容，和我一起探索、学习和成长。欢迎评论区畅所欲言、享受知识的乐趣！
- 推荐：数据分析螺丝钉的首页 格物致知 终身学习 期待您的关注
- 导航：
- LeetCode解锁1000题: 打怪升级之旅：每题都包括3-5种算法，以及详细的代码实现，刷题面试跳槽必备
- 漫画版算法详解：通过漫画的形式和动态GIF图片把复杂的算法每一步进行详细可视解读，看一遍就掌握
- python源码解读：解读python的源代码与调用关系，快速提升代码质量
- python数据分析可视化：企业实战案例：企业级数据分析案例与可视化，提升数据分析思维和可视化能力
- 程序员必备的数学知识与应用：全面详细的介绍了工程师都必备的数学知识
期待与您一起探索技术、持续学习、一步步打怪升级 欢迎订阅本专栏❤️❤️
在本篇文章中，我们将详细解读力扣第156题“上下翻转二叉树”。通过学习本篇文章，读者将掌握如何使用递归和迭代的方法来解决这一问题。每种方法都将配以详细的解释和图解，以便于理解。
问题描述
力扣第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
迭代法
解法思路
迭代法通过栈或队列来模拟递归过程，逐步处理每个节点，实现树的翻转。
步骤
- 初始化当前节点
curr为根节点root，prev为None，next为None，temp为None。 - 迭代处理每个节点：
- 将
next指向当前节点的左子节点。 - 将当前节点的左子节点指向
temp。 - 将
temp指向当前节点的右子节点。 - 将当前节点的右子节点指向
prev。 - 更新
prev为当前节点，curr为next。
- 返回
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 / \ 2 3 / \ 4 5
- 输出：
4 / \ 5 2 / \ 3 1
- 解释：通过递归或迭代方法可以验证树的正确翻转。
- 测试案例 2：
- 输入：
1 / 2 / 3
- 输出：
3 / \ 2 1
- 解释：处理单链的树，确保翻转正确。
总结
本文详细解读了力扣第156题“上下翻转二叉树”，通过递归法和迭代法两种不同的解法，帮助读者深入理解如何高效地实现树的翻转。希望读者通过本文的学习，能够在力扣刷题的过程中更加得心应手。
参考资料
- 《算法导论》—— Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
- 力扣官方题解
🌹🌹如果觉得这篇文对你有帮助的话，记得一键三连关注、赞👍🏻、收藏是对作者最大的鼓励，非常感谢 ❥(^_-)
❤️❤️关注公众号 数据分析螺丝钉 回复 学习资料 领取高价值免费学习资料❥(^_-)
欢迎关注微信公众号 数据分析螺丝钉
