数据结构OJ题——翻转二叉树(Java实现)
2024-01-07 17:11:29
题目链接:翻转二叉树
解题思路:
1.如果根节点(这里为描述方便,记为A)为空,返回null;
2.如果根节点不为空,则"交换"其左子树和右子树;
3.再交换A的左子节点B的左子树和右子树;
4.再交换A的右子节点C的左子树和右子树。
5.最后返回根节点的值。
概括为一句话:遍历整棵树,每经过一个节点就“交换”它的左子树和右子树,直到遍历完所有节点。
这里,“交换”是指,让根节点的左端指向原来的右子树,根节点的右端指向原来的左子树,从而达到翻转的效果。
下面以前序遍历的方式进行代码实现:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode invertTree(TreeNode root) {
//当前根节点为空,说明树为空
if(root == null){
return null;
}
//翻转当前节点下的左子树和右子树,即“交换”
TreeNode node = root.left;
root.left = root.right;
root.right = node;
invertTree(root.left);//翻转左子节点
invertTree(root.right);//翻转右子节点
return root;
}
}
下面以一个具体实例演示代码的执行效果:
总结:本题应用到了两个主要知识点,表面上形象直观的是翻转一棵二叉树,底层抽象出的逻辑是遍历操作和交换两个变量的值。因此,锻炼自身的抽象分析能力很重要。同时这个题目也说明,在二叉树的相关问题中,遍历操作是基础,需要牢固掌握。
文章来源:https://blog.csdn.net/weixin_50759392/article/details/135412507
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!