Java 求解翻转二叉树
2021/11/21 11:40:15
本文主要是介绍Java 求解翻转二叉树,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
文章目录
- 一、题目
- 二、题目分析
- 三、递归法
- 四、非递归法
- 五、层序遍历
- 六、总结
一、题目
翻转一棵二叉树。
二、题目分析
题目要求翻转二叉树,其实只需要把每一个节点左右孩子交换(孩子下面的节点是一起交换的)即可
题目使用前序遍历和后序遍历都可,但是中序遍历不可以,因为中序遍历会把某些节点的左右孩子翻转两次
当然选择层序遍历也是可以的
三、递归法
(1)确定递归参数和返回值
参数就是需要传入节点,返回的也是节点
(2)确定递归终止条件
当前节点为空时,返回
(3)确定单层递归的逻辑
选用前序遍历方式,所以先交换左右子树,然后再递归交换左右子树
class Solution { public TreeNode invertTree(TreeNode root) { //节点为空时,返回 if (root == null) { return null; } //交换左右子树 TreeNode temp = root.left; root.left = root.right; root.right = temp; //递归交换左子树 invertTree(root.left); //递归交换右子树 invertTree(root.right); return root; } }
四、非递归法
依然选择前序遍历,非递归,即迭代借助栈实现
class Solution { public TreeNode invertTree(TreeNode root) { //节点为空时,返回 if (root == null) { return null; } //非递归实现需要借助栈 Deque<TreeNode> deque = new LinkedList<>(); TreeNode node; TreeNode temp; deque.push(root); while (!deque.isEmpty()) { node = deque.pop(); //前序遍历:先处理节点,再入栈左右子树 temp = node.left; node.left = node.right; node.right = temp; if (node.left != null) { deque.push(node.left); } if (node.right != null) { deque.push(node.right); } } return root; } }
五、层序遍历
层序遍历,同样可以实现翻转,遍历过程中交换左右子树的节点即可。
class Solution { public TreeNode invertTree(TreeNode root) { //节点为空时,返回 if (root == null) { return null; } //层序遍历借助队列实现 Deque<TreeNode> deque = new LinkedList<>(); TreeNode node; TreeNode temp; //记录每层有多少节点 int size; deque.add(root); while (!deque.isEmpty()) { size = deque.size(); while (size > 0) { node = deque.poll(); temp = node.left; node.left = node.right; node.right = temp; if (node.left != null) { deque.add(node.left); } if (node.right != null) { deque.add(node.right); } size--; } } return root; } }
六、总结
二叉树的题目,首先选择采用什么遍历方式
前中后序遍历
非递归实现遍历
层序遍历
这篇关于Java 求解翻转二叉树的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南