JAVA 二叉树面试题

简介: JAVA 二叉树面试题

@[TOC]

摘要

  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 二叉树面试题

目录
相关文章
|
16天前
|
监控 Java 应用服务中间件
高级java面试---spring.factories文件的解析源码API机制
【11月更文挑战第20天】Spring Boot是一个用于快速构建基于Spring框架的应用程序的开源框架。它通过自动配置、起步依赖和内嵌服务器等特性,极大地简化了Spring应用的开发和部署过程。本文将深入探讨Spring Boot的背景历史、业务场景、功能点以及底层原理,并通过Java代码手写模拟Spring Boot的启动过程,特别是spring.factories文件的解析源码API机制。
45 2
|
4天前
|
Java 程序员
Java社招面试题:& 和 && 的区别,HR的套路险些让我翻车!
小米,29岁程序员,分享了一次面试经历,详细解析了Java中&和&&的区别及应用场景,展示了扎实的基础知识和良好的应变能力,最终成功获得Offer。
28 14
|
21天前
|
存储 算法 Java
大厂面试高频:什么是自旋锁?Java 实现自旋锁的原理?
本文详解自旋锁的概念、优缺点、使用场景及Java实现。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
大厂面试高频:什么是自旋锁?Java 实现自旋锁的原理?
|
26天前
|
存储 缓存 Oracle
Java I/O流面试之道
NIO的出现在于提高IO的速度,它相比传统的输入/输出流速度更快。NIO通过管道Channel和缓冲器Buffer来处理数据,可以把管道当成一个矿藏,缓冲器就是矿藏里的卡车。程序通过管道里的缓冲器进行数据交互,而不直接处理数据。程序要么从缓冲器获取数据,要么输入数据到缓冲器。
Java I/O流面试之道
|
22天前
|
存储 缓存 Java
大厂面试必看!Java基本数据类型和包装类的那些坑
本文介绍了Java中的基本数据类型和包装类,包括整数类型、浮点数类型、字符类型和布尔类型。详细讲解了每种类型的特性和应用场景,并探讨了包装类的引入原因、装箱与拆箱机制以及缓存机制。最后总结了面试中常见的相关考点,帮助读者更好地理解和应对面试中的问题。
46 4
|
23天前
|
存储 Java 程序员
Java基础的灵魂——Object类方法详解(社招面试不踩坑)
本文介绍了Java中`Object`类的几个重要方法,包括`toString`、`equals`、`hashCode`、`finalize`、`clone`、`getClass`、`notify`和`wait`。这些方法是面试中的常考点,掌握它们有助于理解Java对象的行为和实现多线程编程。作者通过具体示例和应用场景,详细解析了每个方法的作用和重写技巧,帮助读者更好地应对面试和技术开发。
76 4
|
2月前
|
存储 Java 程序员
Java面试加分点!一文读懂HashMap底层实现与扩容机制
本文详细解析了Java中经典的HashMap数据结构,包括其底层实现、扩容机制、put和查找过程、哈希函数以及JDK 1.7与1.8的差异。通过数组、链表和红黑树的组合,HashMap实现了高效的键值对存储与检索。文章还介绍了HashMap在不同版本中的优化,帮助读者更好地理解和应用这一重要工具。
57 5
|
2月前
|
存储 Java
[Java]面试官:你对异常处理了解多少,例如,finally中可以有return吗?
本文介绍了Java中`try...catch...finally`语句的使用细节及返回值问题,并探讨了JDK1.7引入的`try...with...resources`新特性,强调了异常处理机制及资源自动关闭的优势。
23 1
|
SQL 缓存 安全
Java高频面试题目
面试时面试官最常问的问题总结归纳!
146 0
JAVA高频面试题目集锦(6)
JAVA高频面试题目集锦(6)
142 0
JAVA高频面试题目集锦(6)