Java数据结构第十四期：走进二叉树的奇妙世界(三)

news/2025/2/26 15:40:24

专栏：数据结构(Java版)

个人主页：手握风云

目录

一、二叉树OJ练习题

1.1. 相同的树

1.2. 另一棵树的子树

1.3. 翻转二叉树

1.4. 平衡二叉树

1.5. 对称二叉树

一、二叉树OJ练习题

1.1. 相同的树

        判断两棵树是否相同，我们是否只能遍历一遍看结果？看下面的三棵二叉树，上面的树存储的值相同，结构也相同；中间的树存储的值相同，但结构不同；下面的树存储的值不相同。所以我们只遍历一遍看结果不可以。

       我们以相同的方式来遍历两棵二叉树。要判断两棵树结构相同，要么结点同时为空，要么同时不为空。当两个结点都不为空，再去判断结点所存储的值是否相同。先定义两个引用p、q，然后判断根结点是否相同。我们以下图为例，根结点相同、左子树相同且右子树也相同再去判断值相同。如果一个为空，另一个不为空，则结构不同；如果两个引用都不为空，但值不同，也返回false。

完整代码：

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(){}

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

/**
 * 时间复杂度O(min(m.n))
 * m为p这棵树的结点，n为q这棵树的结点
 * 结点小的最先遍历完
 */
public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q){
        if((p != null && q == null) || (p == null && q!= null)){
            return false;
        }

        //上面的if语句不生效，代表要么都为空，要么都不为空
        if(p == null && q == null){
            return true;
        }

        //只剩下都不为空的情况，再判断值是否相同
        if(p.val != q.val){
            return false;
        }

        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
}
public class Test {
    public static void main(String[] args) {
        Solution solution = new Solution();

        TreeNode Tree1 = new TreeNode(1,new TreeNode(2),null);
        TreeNode Tree2 = new TreeNode(1,null,new TreeNode(2));
        System.out.println(solution.isSameTree(Tree1,Tree2));

        TreeNode Tree3 = new TreeNode(1,new TreeNode(2),new TreeNode(3));
        TreeNode Tree4 = new TreeNode(1,new TreeNode(2),new TreeNode(3));
        System.out.println(solution.isSameTree(Tree3,Tree4));

        TreeNode Tree5 = new TreeNode(1,new TreeNode(2),new TreeNode(1));
        TreeNode Tree6 = new TreeNode(1,new TreeNode(1),new TreeNode(2));
        System.out.println(solution.isSameTree(Tree5,Tree6));
    }
}

1.2. 另一棵树的子树

        一棵树的本身就是它的子树，所以我们要首先判断两棵树是否相同，再去判断subRoot是不是等于root的左子树还是右子树，判断我们可以依照上面讲过的是否是相同的树来判断。

完整代码：

class TreeNode{
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(){}

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot){
        if(root == null) {
            return false;
        }

        if(isSameTree(root,subRoot)){
            return true;
        }

        if(isSubtree(root.left,subRoot)){
            return true;
        }

        if(isSubtree(root.right,subRoot)){
            return true;
        }

        return false;
    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if((p != null && q == null) || (p == null && q!= null)){
            return false;
        }

        //上面的if语句不生效，代表要么都为空，要么都不为空
        if(p == null && q == null){
            return true;
        }

        //只剩下都不为空的情况，再判断值是否相同
        if(p.val != q.val){
            return false;
        }

        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
}

public class Test {
    public static void main(String[] args) {
        Solution solution = new Solution();

        TreeNode root = new TreeNode(3,new TreeNode(4),new TreeNode(5));
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(2);

        TreeNode SubRoot = new TreeNode(4,new TreeNode(1),new TreeNode(2));

        System.out.println(solution.isSubtree(root, SubRoot));
    }
}

1.3. 翻转二叉树

        翻转就是把每一个结点的左右孩子都进行交换（如下图所示）。下图可能有一些抽象，我们可以从内存上对二叉树进行一个翻转。只要root不为空，就对左右结点进行交换。当root遍历完整棵二叉树，就可以进行翻转。

完整代码：

class TreeNode{
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(){}

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public TreeNode invertTree(TreeNode root){
        if(root == null){
            return null;
        }

        if(root.left == null && root.right == null){
            return root;
        }

        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;

        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    public void PrevOrder(TreeNode root){
        if(root == null){
            return;
        }
        System.out.print(root.val+" ");
        PrevOrder(root.left);
        PrevOrder(root.right);
    }
}
public class Test {
    public static void main(String[] args) {
        Solution solution = new Solution();
        TreeNode root = new TreeNode(4,new TreeNode(2),new TreeNode(7));
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(9);
        
        System.out.print("翻转之前：");
        solution.PrevOrder(root);
        System.out.println();
        
        solution.invertTree(root);
        
        System.out.print("翻转之后：");
        solution.PrevOrder(root);
    }
}

1.4. 平衡二叉树

        平衡二叉树是指该树所有节点的左右子树的高度相差不超过1。很明显这道题是涉及到求二叉树深度的问题。实现的逻辑也非常简单：求出每棵子树的高度，如果左子树的高度与右子树的高度之差小于等于1，则是平衡二叉树。我们可以调用之前求二叉树的最大深度的方法来求高度。但还存在一种反例（如下图所示）。下面这棵二叉树就不是平衡二叉树，因为9这个的结点的左右子树高度差为2。那么我们就不能只求一次高度，还需要重复计算高度，那么此时的时间复杂度也会随着增大，O(n^{2})。

class TreeNode{
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(){}

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public boolean isBalanced(TreeNode root){
        if(root == null){
            return true;
        }

        int leftHeight = MaxDepth(root.left);
        int rightHeight = MaxDepth(root.right);

        return Math.abs(leftHeight - rightHeight) <= 1
                && isBalanced(root.left)
                && isBalanced(root.right);
    }

    public int MaxDepth(TreeNode root){
        if(root == null){
            return 0;
        }

        int leftH = MaxDepth(root.left);
        int rightH = MaxDepth(root.right);

        return Math.max(leftH,rightH)+1;
    }
}
public class Test {
    public static void main(String[] args) {
        Solution solution = new Solution();

        TreeNode root = new TreeNode(3,new TreeNode(9),new TreeNode(20));
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        System.out.println(solution.isBalanced(root));
    }
}

1.5. 对称二叉树

      要判断二叉树是否是对称的，也就是判断左右子树是否是对称的（如下图所示）。root.left与root.right是否是对称的，再判断下面的子结点是否对称，也就是递归的条件。

class TreeNode{
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(){}

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public boolean isSymmetric(TreeNode root){
        if(root == null){
            return true;
        }
        return isSymmetricChild(root.left,root.right);
    }

    public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree){
        if(leftTree == null && rightTree != null || leftTree != null && rightTree == null){
            return false;
        }

        if(leftTree == null && rightTree == null){
            return true;
        }

        if(leftTree.val != rightTree.val){
            return false;
        }

        return isSymmetricChild(leftTree.left,rightTree.right)
                && isSymmetricChild(leftTree.right,rightTree.left);
    }
}

public class Test {
    public static void main(String[] args) {
        Solution solution = new Solution();
        TreeNode root = new TreeNode(1,new TreeNode(2),new TreeNode(2));

        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(3);

        System.out.println(solution.isSymmetric(root));
    }
}


http://www.niftyadmin.cn/n/5868897.html

相关文章

vscode中使用PlatformIO创建工程加载慢

vscode中使用PlatformIO创建工程加载慢

最近使用vscodeplatformIO开发esp32s3&#xff0c;第一次创建工程时加载速度很慢&#xff0c;查询资料解决问题&#xff0c;特此记录。 1.新建环境变量pyhton 此电脑-属性-高级系统设置中&#xff08;直接搜索高级系统设置也行&#xff09;&#xff0c;添加系统变量&#xff…
阅读更多...
腾讯云安全加速：应对网络攻击与访问延迟的现实挑战

腾讯云安全加速：应对网络攻击与访问延迟的现实挑战

​​​​​​ 随着互联网业务的全球化发展&#xff0c;企业面临着网络攻击、访问延迟、跨境访问不稳定等问题。无论是电商、金融、在线教育&#xff0c;还是 SaaS 平台&#xff0c;用户体验的流畅性与安全性都直接影响着业务成败。而DDoS 攻击、爬虫、数据泄露等安全威胁不断增…
阅读更多...
R-INLA实现绿地与狐狸寄生虫数据空间建模：含BYM、SPDE模型及PC先验应用可视化...

R-INLA实现绿地与狐狸寄生虫数据空间建模：含BYM、SPDE模型及PC先验应用可视化...

全文链接&#xff1a;https://tecdat.cn/?p40720 本论文旨在为对空间建模感兴趣的研究人员客户提供使用R-INLA进行空间数据建模的基础教程。通过对区域数据和地统计&#xff08;标记点&#xff09;数据的分析&#xff0c;介绍了如何拟合简单模型、构建和运行更复杂的空间模型&…
阅读更多...
数据分析——Pandas 中的 apply() 函数

数据分析——Pandas 中的 apply() 函数

apply() 是 Pandas 中最灵活且强大的函数之一&#xff0c;它允许你 自定义操作逻辑&#xff0c;并将其应用到 DataFrame 或 Series 的行、列或分组中。本文通过实战案例&#xff0c;帮你彻底掌握 apply() 的核心用法。 一、基础概念&#xff1a;什么是 apply()&#xff1f; ap…
阅读更多...
《2025国内免费DeepSeek-R1自部署平台实测指南：三大运营商/腾讯/华为哪家强？附避坑清单》

《2025国内免费DeepSeek-R1自部署平台实测指南：三大运营商/腾讯/华为哪家强？附避坑清单》

更新日期&#xff1a;2025年2月24日 | 实测时效性声明&#xff1a;部分服务可能因政策调整限流或下线&#xff0c;建议结合最新信息参考。 一、前言&#xff1a;为什么关注DeepSeek-R1自部署&#xff1f; DeepSeek-R1-671B作为国内首个千亿级开源模型&#xff0c;其“满血版”…
阅读更多...
MTK Android12 预装apk可卸载

MTK Android12 预装apk可卸载

文章目录 需求解决方法1、device/mediatek/mt6761/device.mk2、/vendor/mediatek/proprietary/frameworks/base/data/etc/pms_sysapp_removable_vendor_list.txt3、路径&#xff1a;4、Android.mk 需求 近期&#xff0c;客户需要预装一个apk&#xff0c;同时该apk要可卸载。解…
阅读更多...
希尔排序：突破插入排序的局限

希尔排序：突破插入排序的局限

大家好&#xff01;今天我们要介绍的是一种改进的插入排序算法——希尔排序&#xff08;Shell Sort&#xff09;。希尔排序通过“分组插入”的方式&#xff0c;突破了传统插入排序的局限性&#xff0c;大大提高了排序效率。虽然它不是最理想的排序算法&#xff0c;但由于简单且…
阅读更多...
JavaScript基础（函数及面向对象）

JavaScript基础（函数及面向对象）

函数 定义函数 Java定义方法&#xff1a; public 返回值类型 方法名(){ return 返回值 } 定义函数方法一 eg&#xff1a;定义一个绝对值函数 function abs(x) {if (x>0){return x;}else {return -x;}} 调用函数&#xff1a; 注意&#xff1a;一旦执行到return代表函数…
阅读更多...
最新文章

Copyright @ 2022~2023