首页 > 其他分享 >二叉树 - 二叉树入门题

二叉树 - 二叉树入门题

时间:2024-01-19 13:01:24浏览次数:32  
标签:right TreeNode 入门 二叉树 return null root left

二叉树入门题

1. 判断两颗树是否相同

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 如何判断两颗树是否相同? 根相同 + 左右子树相同
        // 如何判断根相同? 结构 + 值相同
        if (p == null && q != null || p != null && q == null) {
            return false;
        }
        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);
    }
}

时间复杂度分析:

假设,p树节点个数为N q树节点个数为M 

时间复杂度为 O(min(N,M)), 因为最坏情况下遍历完节点少的树就停止了

2. 判断一颗树是否是另一颗树的子树

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 如何判断两颗树是否相同? 根相同 + 左右子树相同
        // 如何判断根相同? 结构 + 值相同
        if (p == null && q != null || p != null && q == null) {
            return false;
        }
        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 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;
    }
    
}

时间复杂度分析:

设树节点为M 子树节点为N

最坏情况下,树中每一个节点都判断一次(调用isSameTree) 时间复杂度为O(M*N)

3. 翻转一颗二叉树

/**
 * 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;
        }
        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;
    }
}

4. 判断一颗树是否是平衡二叉树

如何判断 平衡二叉树 ? 每颗树的左右高度差 <= 1

class Solution {
    public int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return Math.max(leftHeight, rightHeight) + 1;
    }

    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        int leftH = getHeight(root.left);
        int rightH = getHeight(root.right);
        if (Math.abs(leftH - rightH) <= 1 
        && isBalanced(root.left) && isBalanced(root.right)) {
            return true;
        }
        return false;
    }
}

时间复杂度分析:

能否以O(N)时间复杂度 判断一颗树是否为平衡二叉树 ?

在计算高度的同时进行判断

 

class Solution {
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) >= 0;
    }
    public int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftH = getHeight(root.left);
        int rightH = getHeight(root.right);
        if (leftH >= 0 && rightH >= 0 && Math.abs(leftH - rightH) <= 1) {
            return Math.max(leftH,rightH) + 1;
        }else {
            return -1;
        }
    }
}

5. 判断对称二叉树

class Solution {
    public boolean isSymmetric(TreeNode root) {
        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);
    }
}

 

标签:right,TreeNode,入门,二叉树,return,null,root,left
From: https://www.cnblogs.com/xumu7/p/17972998

相关文章

  • Python编程语法零基础入门
    0.开始前了解#号是一行注释"""6个"是多行注释"""#--coding:UTF-8print(u"你好!")#中文加上u转为unicode显示,不然会显示乱码1.基础语法和概念#(1)基本数据结构(整型、浮点型、字符串、布尔型)#格式:name=value没有分号、编译器自动匹配类型int_num=10float_num=......
  • kafka入门(八):副本
    副本kafka副本之间是一主多从的关系。其中leader副本负责处理读写请求,follower副本只负责与leader副本的消息同步。副本处于不同的broker中,当leader副本出现故障时,从follower副本中重新选举新的leader副本对外提供服务。kafka通过多副本机制实现了故障的自动转......
  • 普普通通入门js案例(原生)
    数组中数据的遍历 vararr=[34,3,4,3]; for(i=0;i<arr.length;i++){ console.log(arr[i]); }求数组中的最大值 vararr=[34,3,4,3]; max=arr[0]; for(i=1;i<arr.length;i++){ if(max<arr[i]){ max=arr[i]; } }求数组中的平......
  • day 02java入门之Hello.java
    java命令行执行(注意代码编写用GBK,命令行窗口用GBK进行解析)注意public类名要和文件名一致,一个.java文件中最多只有一个public类java注意事项一个.java文件中若含有多个类时,编译完成后会生成相应个数的.class文件......
  • 跨语言调用神器SWIG介绍与使用入门
    安装依赖PCRE库apt-getinstalllibpcre2-dev下载安装$./configure$make$makeinstall介绍SWIG是一个软件开发工具,能够简化不同编程语言与C和C++程序连接的开发任务。简而言之,SWIG是一款编译器,它可以获取C/C++声明并创建访问这些声明所需的包装器,从而可从......
  • Web前端新手入门系列:案例1 招商银行页面的制作
    一次比较复杂的网页设计(对初学者而言)效果图代码可能不太符合规范,但效果差不多(HTML部分<!DOCTYPEhtml><htmllang="en"xmlns="http://www.w3.org/1999/xhtml"><head><metacharset="utf-8"/><title>招商银行</title>&......
  • xapian 搜索引擎介绍与使用入门
    Xapian是一个开源搜索引擎库,使用C++编写,并提供绑定(bindings )以允许从多种编程语言使用。它是一个高度适应性的工具包,允许开发人员轻松地将高级索引和搜索功能添加到自己的应用程序中。Xapian支持多种加权模型和丰富的布尔查询运算符。最新稳定版本是1.4.24,发布于2023年......
  • Istio从入门到精通—— 安装 —— Kubernetes 删除 istio-system namesapce 时候,出现
    Kubernetes删除istio-systemnamesapce时候,出现Terminating解决办法当你在Kubernetes中遇到无法删除处于Terminating状态的命名空间时,可能是由于该命名空间中仍有活跃的资源或服务。要解决这个问题,你可以尝试以下几个步骤:一、常规方法检查命名空间中的活跃资源:......
  • 入门Linux运维工程师需要掌握的知识点和工具以及技能
    Linux系统的学习,可以选用redhat或centos,特别是centos在企业中用得最多,当然还会有其它版本的,比如Ubuntu等,根据自己的工作情况和兴趣来定。当然不同发行版本主要是包上的区别以及一些命令的差异,其他内核上的东西都大同小异。对于刚入门或准备入门Linux运维的来说,整理总结了以下10个......
  • 二叉树结构与递归实现前中后序遍历
    1.二叉树结构2.二叉树节点遍历顺序前序:每颗子树以中—》左—》右遍历ABDEHCFG 中序:每颗子树以左 —》中—》右遍历DBEHAFCG 后序:每颗子树以左 —》右—》中遍历DHEBFGCA 代码实现:publicclassBinaryTree{stat......