首页 > 编程语言 >JAVA 二叉树面试题

JAVA 二叉树面试题

时间:2024-11-01 14:09:38浏览次数:3  
标签:node Node 面试题 return 二叉树 JAVA null 节点

@

目录

摘要

  1. 问题1:求二叉树的最大深度
  2. 问题2:求二叉树的最小深度
  3. 问题3:求二叉树中节点的个数
  4. 问题4:求二叉树中叶子节点的个数
  5. 问题5:求二叉树中第k层节点的个数(不是求第k层叶子节点个数)
  6. 问题6:判断两棵树是否相同
  7. 问题7:给定一个二叉树,检查它是否是镜像对称的。
  8. 问题8:(递归)二叉树的前序遍历
  9. 问题9:(递归)二叉树的中序遍历
  10. 问题10:(递归)二叉树的后序遍历

代码

Node节点

import lombok.Data;

/**
 * 二叉树数据结构
 * @author: liudz
 * @date: 2021/4/8
 */
@Data
public class Node {
    int val;//节点数据
    Node left;//左子节点的引用
    Node right;//右子节点的引用

    public Node() {};

    public Node(int val) {
        this.val = val;
        left = null;
        right = null;
    }

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

main函数

public static void main(String[] args){
        Node p1 = new Node(1, new Node(2), new Node());
        Node q1 = new Node(1, new Node(), new Node(2));

        /*   a1:↓                           a2:↓                  a3:↓
                1                               1                     1
               / \                                                   / \
              2   3                                                 2   3
             / \
            4   5
               /
              6
         */
        Node a1 = new Node(1, new Node(2, new Node(4), new Node(5, new Node(6), null)), new Node(3));
        Node a2 = new Node(1, null, null);
        Node a3 = new Node(1, new Node(2, null, null), new Node(3, null, null));

        //问题10:(递归)二叉树的后序遍历
//        postOrderRe(a1).stream().forEach(item -> System.out.print(item + " "));

        //问题9:(递归)二叉树的中序遍历
//        midOrderRe(a1).stream().forEach(item -> System.out.print(item + " "));

        //问题8:(递归)二叉树的前序遍历
//        preOrderReverse(a1).stream().forEach(item -> System.out.print(item + " "));

        //问题5:求二叉树中第k层节点的个数(不是求第k层叶子节点个数)
//        System.out.println("numsOfkLevelTreeNode:" + numsOfkLevelTreeNode(a1, 3));

        //问题4:求二叉树中叶子节点的个数
//        System.out.println("numsOfNoChildNode:" + numsOfNoChildNode(a1));

        //问题3:求二叉树中节点的个数
//        System.out.println("numOfTreeNode:" + numOfTreeNode(a1));

        //问题2:求二叉树的最小深度
//        System.out.println("mintreeDepth:" + mintreeDepth(a1));

        //问题1:求二叉树的最大深度
//        System.out.println("maxtreeDepth:" + maxtreeDepth(a1));

        //问题7:给定一个二叉树,检查它是否是镜像对称的。
//        System.out.println(isSymmetric(p1, q1));
        
        //问题6:判断两棵树是否相同
//        System.out.println(isSameTree(p1, q1));
        
    }

问题1:递归——求二叉树的最大深度

/**
    * 问题1:递归——求二叉树的最大深度
    * @param node node
    * @Author liudz 
    * @Date 2021/6/29  
    * @return 
    */
    public static int maxtreeDepth(Node node){
        if (node == null) {
            return 0;
        }
        return Math.max(maxtreeDepth(node.getLeft()), maxtreeDepth(node.getRight())) + 1;
    }

问题2:求二叉树的最小深度

/**
     * 问题2:求二叉树的最小深度
     * @param node node
     * @Author liudz
     * @Date 2021/6/29
     * @return
     */
    public static int mintreeDepth(Node node){
        if (node == null) {
            return 0;
        }
        return Math.min(mintreeDepth(node.getLeft()), mintreeDepth(node.getRight())) + 1;
    }

问题3:求二叉树中节点的个数

/**
     * 问题3:求二叉树中节点的个数
     * @param node node
     * @Author liudz
     * @Date 2021/6/29
     * @return
     */
    public static int numOfTreeNode(Node node){
        if (node == null) {
            return 0;
        }
        return numOfTreeNode(node.getLeft()) + numOfTreeNode(node.getRight()) + 1;
    }

问题4:求二叉树中叶子节点的个数

/**
     * 问题4:求二叉树中叶子节点的个数
     * @param node node
     * @Author liudz
     * @Date 2021/6/29
     * @return
     */
    public static int numsOfNoChildNode(Node node){
        if (node == null) {
            return 0;
        }
        if (node.getLeft() == null && node.getRight() == null) {
            return  1;
        }
        return numsOfNoChildNode(node.getLeft()) +  numsOfNoChildNode(node.getRight());
    }

问题5:求二叉树中第k层节点的个数,不是求第k层叶子节点个数

/**
     * 问题5:求二叉树中第k层节点的个数,不是求第k层叶子节点个数
     * @param node node
     * @Author liudz
     * @Date 2021/6/29
     * @return
     */
    public static int numsOfkLevelTreeNode(Node node, int level){
        if (node == null || level <= 0) {
            return 0;
        }
        if (node != null && level == 1) {
            return 1;
        }
        return numsOfkLevelTreeNode(node.getLeft(), level-1) +  numsOfkLevelTreeNode(node.getRight(), level-1);
    }

问题6:判断两棵树是否相同

/**
     *  问题6:判断两棵树是否相同
     *  思路:方法一:深度优先搜索
     *      如果两个二叉树都为空,则两个二叉树相同。
     *      如果两个二叉树中有且只有一个为空,则两个二叉树一定不相同。
     *      如果两个二叉树都不为空,那么首先判断它们的根节点的值是否相同,若不相同则两个二叉树一定不同,
     *                          若相同,再分别判断两个二叉树的左子树是否相同以及右子树是否相同。
     * 这是一个递归的过程,因此可以使用深度优先搜索,递归地判断两个二叉树是否相同。
     * @param p p
     * @param q q
     * @author liudz
     * @date 2021/4/21
     * @return 执行结果
     **/
    public static boolean isSameTree(Node p, Node q) {
        if (p == null && q == null) {
            return true;
        } else if (p == null || q  == null) {
            return false;
        } else if (p.getVal() != q.getVal()) {
            return false;
        } else {
            return isSameTree(p.getLeft(), q.getLeft()) && isSameTree(p.getRight(), q.getRight());
        }
    }

问题7:给定一个二叉树,检查它是否是镜像对称的。

/**
     *  问题7:给定一个二叉树,检查它是否是镜像对称的。
     *  思路:(类似判断两棵树是否相同)
     *      如果两个二叉树都为空,则两个二叉树相同。
     *      如果两个二叉树中有且只有一个为空,则两个二叉树一定不相同。
     *      如果两个二叉树都不为空,那么首先判断它们的根节点的值是否相同,若不相同则两个二叉树一定不同,
     *                          若相同,再分别判断一棵树的左子树和另一棵树的右子树是否相同
     * @author liudz
     * @date 2021/4/21
     * @return 执行结果
     **/
    public static boolean isSymmetric(Node p, Node q) {
        if (p == null && q == null) {
            return true;
        } else if (p == null || q == null) {
            return false;
        }else if (p.getVal() != q.getVal()) {
            return false;
        }
        return isSymmetric(p.getLeft(), q.getRight()) && isSymmetric(p.getRight(), q.getLeft());

    }

问题8:(递归)二叉树的前序遍历

/**
     * 问题8:(递归)二叉树的前序遍历
     *    问题:为啥分2个方法而不是写一个方法?
     *    答案:因为写一起每次ArrayList都会重新初始化,导致结果不对
     * 思路:封装递归方法
     *      1)根节点值添加list + 2)递归左节点  3)递归右节点
     * @param node node
     * @Author liudz
     * @Date 2021/6/29
     * @return
     */
    public static List preOrderReverse(Node node){
        List list = new ArrayList();
        preOrder(node, list);
        return list;
    }
    public static void  preOrder(Node node, List list) {
        if (node == null) {
            return;
        }
        list.add(node.getVal());
        preOrder(node.getLeft(), list);
        preOrder(node.getRight(), list);
    }

问题9:(递归)二叉树的中序遍历

/**
     * 问题9:(递归)二叉树的中序遍历
     *    问题:为啥分2个方法而不是写一个方法?
     *    答案:因为写一起每次ArrayList都会重新初始化,导致结果不对
     * @param node node
     * @Author liudz
     * @Date 2021/6/29
     * @return
     */
    public static List midOrderRe(Node node){
        ArrayList list = new ArrayList();
        midOrder(node, list);
        return list;
    }
    public static void  midOrder(Node node, List list) {
        if (node == null) {
            return;
        }
        midOrder(node.getLeft(), list);
        list.add(node.getVal());
        midOrder(node.getRight(), list);
    }

问题10:(递归)二叉树的后序遍历

 /**
     * 问题10:(递归)二叉树的后序遍历
     *    问题:为啥分2个方法而不是写一个方法?
     *    答案:因为写一起每次ArrayList都会重新初始化,导致结果不对
     * @param node node
     * @Author liudz
     * @Date 2021/6/29
     * @return
     */
    public static List postOrderRe(Node node){
        ArrayList list = new ArrayList();
        postOrder(node, list);
        return list;
    }
    public static void  postOrder(Node node, List list) {
        if (node == null) {
            return;
        }
        postOrder(node.getLeft(), list);
        postOrder(node.getRight(), list);
        list.add(node.getVal());
    }

本人其他文章链接

1.单链表题+数组题(快慢指针和左右指针)

2.BFS(Breath First Search 广度优先搜索)

3.”回溯算法“框架及练习题

4.JAVA 二叉树面试题

标签:node,Node,面试题,return,二叉树,JAVA,null,节点
From: https://www.cnblogs.com/bigcat26/p/18520025

相关文章

  • 为什么 C++ 编译速度比 Java 慢得多
    ###为什么C++编译速度比Java慢得多在探讨为什么C++编译速度比Java慢得多时,我们可以归纳出几个核心原因:C++的编译模型更为复杂、模板元编程、宏处理以及链接时间。其中,C++的编译模型更为复杂这一点尤为突出。C++需要处理的细节更多,如模板实例化、头文件的重复包含等,这些......
  • Java 传参时,如何做到两个 String 实参的实际值交换_3
    ###Java传参时,如何做到两个String实参的实际值交换在Java中,所有的参数传递都是值传递,这意味着方法接收的是实参值的一个副本。对于基本数据类型,这个副本是实际值;对于对象,副本是引用的一个拷贝。因此,直接在方法内部交换两个`String`实参的实际值是不可能的。然而,可以通过一......
  • 一文彻底熟练掌握并使用Java的NIO操作
    一、基本概念JavaNIO是Java1.4引入的,用于处理高速、高并发的I/O操作。与传统的阻塞I/O不同,NIO支持非阻塞I/O和选择器,可以更高效地管理多个通道。二、核心组件通道(Channel)Channel是NIO中用于读取和写入数据的主要接口,提供双向数据传输的能力。常见的通道实现......
  • 基于Java的医疗保险报销系统设计与实现
    基于Java语言、Spring框架、SpringBoot、HTML/CSS/JavaScript、Vue、Jwt、Element-ui等技术,进行医疗保险报销系统的设计。本系统旨在将医疗保险报销系统中的分散信息进行归纳与整合,对其进行统一的信息管理,使其整个报销流程更加的系统化、科学化、透明化。在医疗保险报销系统......
  • 数据结构与算法(二叉树)
    鲸饮未吞海,剑气已横秋。 前言  这是我学习数据结构的第五份笔记,有关二叉树的知识。后期我会继续将数据结构知识的笔记补全。 上一期笔记有栈与列队,没看过的同学可以去看看:有关栈与列队的笔记https://blog.csdn.net/hsy1603914691/article/details/143064674?spm=10......
  • Java-SE-泛型编程-总结/java
    泛型一、泛型的定义和使用类定义:在定义一个泛型类时,需要在类名后加上<T>,以指示这是一个泛型类。例如:publicclassPair<T>{...}方法定义:在定义泛型方法时,需要在返回类型前加上<T>,这样编译器才会知道这是一个泛型方法。例如:public<T>Tadd(Pair<T>p){...}......
  • JAVA开发笔记之mac基于jenv管理多java版本
    0x00本文主要记录mac上jenv管理多版本java的坑;前提是配置好brew镜像,确保brewupdate会正常执行而不是卡住。 0x01安装jenvbrewinstalljenv#添加jenv环境变量,修改用户文件夹下对应的~/.bash_profile或者~/.zhsrcexportPATH="$HOME/.jenv/bin:$PATH"eval"$(jenvi......
  • java+vue计算机毕设高校毕业生就业管理系统的设计与实现【开题+程序+论文+源码】
    本系统(程序+源码)带文档lw万字以上文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容研究背景随着高等教育的普及和毕业生人数的逐年攀升,高校毕业生就业问题已成为社会各界关注的焦点。传统的就业管理模式在信息处理、资源匹配及效率提升方面已......
  • Java读取properties配置文件
    需要导入的jar<dependency><groupId>org.springframework</groupId><artifactId>spring-core</artifactId><version>5.3.14</version></dependency>方法:使用Spring PropertiesLoaderUtils.loadProperties();方法一......
  • 基于Java+SpringBoot+Vue+HTML5同城上门喂遛宠物系统(源码+LW+调试文档+讲解等)/同城
    博主介绍......