当前位置： 首页 > news >正文

二叉树的操作及常见面试题

news 来源：原创 2024/9/21 17:45:00

文章目录

  • 前言
  • 一、四种遍历方式
  • 二、二叉树的基本操作
      • 2.1 统计二叉树的结点个数
      • 2.2 统计二叉树的叶子结点个数
      • 2.3 求二叉树第K层节点个数
      • 2.4 求二叉树的高度
      • 2.5 判断一棵树中是否包含指定的值
  • 三、二叉树的基础面试题
      • 3.1 相同的树
      • 3.2 另一棵树的子树
      • 3.3 平衡二叉树
  • 总结

前言

上一篇博主归纳了一下二叉树的基本概念以及性质：

二叉树的概念及性质

本文将附上博主自己手动实现的二叉树常见的各种操作以及归纳总结一下常见的基础面试题。

一、四种遍历方式

二叉树额所有问题最终都是四种遍历方式的衍生问题。

前、中、后序遍历为深度优先遍历（DFS），借助“栈”结构

如图：

在这里插入图片描述
1.前序遍历：

ABDEGHCF

先访问根节点，然后递归访问左子树，再递归访问右子树，根左右

递归写法：

public class PreorderTraversal {
    List<Integer> ret = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if(root==null){
            return ret;
        }
        ret.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return ret;
    }
}

迭代写法：

public class Preorder {
    List<Integer> list = new ArrayList<>();
    Deque<TreeNode> stack = new LinkedList<>(); //借助辅助栈
    public List<Integer> preorder(TreeNode root) {
        if (root == null){
            return list;
        }
        TreeNode cur = root;
        while (!stack.isEmpty() || cur!=null){  //右边这个条件是防止弹出根节点后，右子树还有结点的情况
            while (cur!=null){
                stack.push(cur);
                list.add(cur.val);
                cur = cur.left;
            }
            // 走到这里的时候左子树已经走到了最左下，该弹出最坐下结点，开始访问右子树了
            cur=stack.pop();
            cur = cur.right;
        }

        return list;
    }
}

2.中序遍历：

DBGHEACF

先递归左子树，再根，最后递归右子树，左根右 => 先一路向左走到根儿~’

递归写法：

public class InorderTraversal {
    List<Integer> ret = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if (root==null) {
            return ret;
        }
        inorderTraversal(root.left);
        ret.add(root.val);
        inorderTraversal(root.right);
        return ret;
    }
}

迭代写法：

public class InorderTraversal {
    public List<Integer> inorder(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        if (root == null){
            return list;
        }
        TreeNode cur = root;
        while (!stack.isEmpty() || cur!=null){
            while (cur!=null){
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            list.add(cur.val);
            cur = cur.right;
        }
        return list;
    }
}

3.后序遍历：

DHGEBFCA

先递归左子树再递归右子树，最后根先一路向左走到根儿~~

递归写法：

public class PostorderTraversal {
    List<Integer> ret=new ArrayList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        if (root==null){
            return ret;
        }
        postorderTraversal(root.left);
        postorderTraversal(root.right);
        ret.add(root.val);
        return ret;
    }
}

迭代写法：

public class Postorder {
    public List<Integer> postorder(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }

        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode prev = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            /**
             * 前面都一样走到最左边，后面加个if判断：每次弹栈就判断当前结点是否应该处理结束，若右子树为空或者右子树处理过了，那就处理当前
             */
            if (root.right == null || root.right == prev) {
                res.add(root.val); //当前root结点就是已经处理结束的结点
                prev = root; //所以 prev指向了最新的处理结束的结点，以前的不管了反正都结束了
                root = null;
            } else {  //否则，把当前结点压回栈中
                stack.push(root);
                root = root.right;
            }
        }
        return res;
    }
}

层序遍历为广度优先遍历（BFS），借助队列结构

4.层序遍历：

从二叉树的第一层开始一层层向下遍历，每一层由左至右开始遍历

ABCDEFGH

 public void levelOrder(TreeNode<E> root) {
        Deque<TreeNode<E>> queue = new LinkedList<>();
        queue.offer(root);
        // 循环的终止条件就是队列为空
        while (!queue.isEmpty()) {
            // 取出当前层的节点个数，每当进行下一次遍历的时候，队列中就存储了该层的所有元素
            int n = queue.size();
            for (int i = 0; i < n; i++) {
                TreeNode<E> node = queue.poll();
                System.out.print(node.val + " ");
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
    }

递归把握语义，巧妙使用递归函数的作用帮助我们辅助解决问题。

注意事项：

1.先序遍历的第一个结果一定是当前二叉树的根节点
2.中序遍历左子树的结果一定再根节点左侧，右子树的遍历结果在根节点右侧
3.后序遍历的最后一个结果是当前二叉树的根节点，将后序遍历的结果集reverse得到一个先序遍历的镜像结果集 “根右左”

二、二叉树的基本操作

2.1 统计二叉树的结点个数

在这里插入图片描述

递归：

public int getNodes(TreeNode<?> root) {
        return root == null ? 0 : 1 + getNodes(root.left) + getNodes(root.right);
    }

非递归：

public int getNodesNonRecursion(TreeNode<?> root) {
        if (root == null) {
            return 0;
        }
        Deque<TreeNode<?>> queue = new LinkedList<>();
        queue.offer(root);
        int num = 0;
        while (!queue.isEmpty()) {
            TreeNode temp = queue.poll();
            num++;
            if (temp.left != null) {
                queue.offer(temp.left);
            }
            if (temp.right != null) {
                queue.offer(temp.right);
            }
        }
        return num;
    }

2.2 统计二叉树的叶子结点个数

总叶子结点个数 = 左树中的叶子结点个数 + 右树中的叶子结点个数

代码如下：

public int getLeafNodes(TreeNode<?> root) {
        // 1.边界
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            // 只有root,root就是一个叶子结点
            return 1;
        }
        // 此时root不为空，也有子树，总叶子结点个数 = 左树中的叶子结点个数 + 右树中的叶子结点个数
        return getLeafNodes(root.left) + getLeafNodes(root.right);
    }

2.3 求二叉树第K层节点个数

求以root为根的第k层结点个数 = 以root.left为根的第k - 1层结点个数 + 以root.right为根的第k - 1层结点个数

在这里插入图片描述
代码如下：

 /**
     * 传入一颗以root为根的二叉树，就能求出第k层的节点个数 k <= height(root)
     *
     * @return
     */
    public int getKLevelNodes(TreeNode root, int k) {
        // 1.边界条件
        if (root == null || k <= 0) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        // 求以root为根的第k层结点个数 = 以root.left为根的第k - 1层结点个数 + 以root.right为根的第k - 1层结点个数
        return getKLevelNodes(root.left, k - 1) + getKLevelNodes(root.right, k - 1);
    }

2.4 求二叉树的高度

当前树高等于1+左右子树中的最大树高

在这里插入图片描述代码如下：

/**
     * 传入一颗以root为根的二叉树，就能求出该树的高度是多少
     *
     * @param root
     * @return
     */
    public int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + Math.max(height(root.left), height(root.right));
    }

2.5 判断一棵树中是否包含指定的值

代码如下：

/**
     * 判断以root为根的二叉树中是否包含指定值val
     *
     * @param root
     * @param val
     * @return
     */
    public boolean contains(TreeNode<E> root, E val) {
        if (root == null) {
            return false;
        }
        if (root.val.equals(val)) {
            return true;
        }
        // 继续在左子树和右子树中寻找是否包含指定值
        return contains(root.left, val) || contains(root.right, val);
    }

三、二叉树的基础面试题

3.1 相同的树

在这里插入图片描述思路：

相同的树就是当前结点相同并且其左右子树的结点也相同，递归实现十分容易。

代码如下：

/**
 * 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 boolean isSameTree(TreeNode p, TreeNode q) {
        if (p==null){
            if (q==null){return true;}
            return false;
        }
        if (q==null){
            if (p==null){return true;}
            return false;
        }
        if (p.val== q.val){
            return (isSameTree(p.left,q.left)) && (isSameTree(p.right,q.right));
        }
        return false;
    }
}

3.2 另一棵树的子树

在这里插入图片描述

思路：

本题基于上一题，然后从根节点先序遍历来逐一判断当前结点是否为相同的树。

  1. 判断root和subRoot是不是就是相同的树 true
  2. root.left或者root.right 中判断是否包含subRoot

判断root中是否包含subRoot => root和subRoot就是相同的树 || root.left中是否包含subRoot || root.right中是否包含subRoot

这三个条件有一个满足，就认为root包含subRoot

代码如下：

public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p==null){
            if (q==null){return true;}
            return false;
        }
        if (q==null){
            if (p==null){return true;}
            return false;
        }
        if (p.val== q.val){
            return (isSameTree(p.left,q.left)) && (isSameTree(p.right,q.right));
        }
        return false;
    }
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        // 边界
        if (root == null && subRoot == null) {
            return true;
        }
        if (root == null || subRoot == null) {
            return false;
        }
        // 恰好root和subRoot就是相同的树 => true
        if (isSameTree(root,subRoot)){
            return true;
        }
        if (isSubtree(root.left,subRoot)){
            return true;
        }
        if (isSubtree(root.right,subRoot)){
            return true;
        }
        return false;
//        return isSameTree(root,subRoot) || isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
    }

3.3 平衡二叉树

在这里插入图片描述

    public int treeTall(TreeNode root){
        if (root==null){
            return 0;
        }
        return 1+Math.max(treeTall(root.left),treeTall(root.right));

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

总结

以上是二叉树的常见操作以及基础面试题，博主之后会更新二叉树的进阶面试题，于💪扣官方给的题解更通俗易懂一点，希望老铁们多多支持，点个关注和赞，感谢！😁😁😁😁

相关文章：

  • 北京网站建设多少钱？
  • 辽宁网页制作哪家好_网站建设
  • 高端品牌网站建设_汉中网站制作
  • 手把手教—搭建vite+vue3+ts+pinia+element-plus+qiankun项目（新增部分vite实用插件介绍）
  • Keepalived实现高可用
  • Nginx入门（简介、反向代理、负载均衡）
  • hrbust0J月赛myj的尘歌壶—dfs（走迷宫）
  • 【TS系列】TypeScript进阶（二）
  • 【Linux】Linux基本操作（一）：初识操作系统、ls、cd、touch、mkdir、pwd
  • FPGA之旅设计99例之第十九例----OV5640上电及初始化
  • m基于matlab的GPS卫星信号捕获和数据解析仿真
  • 场景应用：Spring容器是一个什么样的概念？有什么作用？应用上下文呢？
  • 2022 年 TI 杯大学生电子设计竞赛具有自动泊车功能的电动车（B 题）——小车视觉神经网络模型压缩的解决办法（流媒体、嵌入式端）
  • 【网站】作为技术人可能要用到的IT技术网址清单，欢迎评论补充
  • 改进YOLOv7系列：最新结合DO-DConv卷积、Slim范式提高性能涨点，打造高性能检测器
  • 基础IO之文件操作
  • 【openGauss笔记】SQL语法- 10视图与物化视图
  • 【漏洞复现-thinkphp-命令执行】vulfocus/thinkphp-3.2.x
  • 【剑指offer】让抽象问题具体化
  • 【腾讯Bugly干货分享】从0到1打造直播 App
  • 002-读书笔记-JavaScript高级程序设计 在HTML中使用JavaScript
  • 2018天猫双11|这就是阿里云！不止有新技术，更有温暖的社会力量
  • C++11: atomic 头文件
  • java 多线程基础, 我觉得还是有必要看看的
  • JAVA之继承和多态
  • Material Design
  • mockjs让前端开发独立于后端
  • MySQL QA
  • MySQL用户中的%到底包不包括localhost?
  • SpringCloud集成分布式事务LCN (一)
  • Sublime text 3 3103 注册码
  • V4L2视频输入框架概述
  • Vultr 教程目录
  • 从零到一：用Phaser.js写意地开发小游戏（Chapter 3 - 加载游戏资源）
  • 从零开始在ubuntu上搭建node开发环境
  • 对象引论
  • 深入 Nginx 之配置篇
  • 我的zsh配置, 2019最新方案
  • ionic入门之数据绑定显示-1
  • zabbix3.2监控linux磁盘IO
  • 阿里云移动端播放器高级功能介绍
  • ​​​​​​​​​​​​​​Γ函数
  • ​【C语言】长篇详解，字符系列篇3-----strstr，strtok，strerror字符串函数的使用【图文详解​】
  • ​ArcGIS Pro 如何批量删除字段
  • ​批处理文件中的errorlevel用法
  • ‌‌雅诗兰黛、‌‌兰蔻等美妆大品牌的营销策略是什么？
  • （1）Nginx简介和安装教程
  • （备忘）Java Map 遍历
  • （二十四）Flask之flask-session组件
  • （附源码）node.js知识分享网站 毕业设计 202038
  • (附源码)计算机毕业设计高校学生选课系统
  • (紀錄)[ASP.NET MVC][jQuery]-2 純手工打造屬於自己的 jQuery GridView (含完整程式碼下載)...
  • (七)glDrawArry绘制
  • （三） diretfbrc详解
  • (循环依赖问题)学习spring的第九天
  • .gitignore文件_Git：.gitignore
  • .NET 3.0 Framework已经被添加到WindowUpdate
  • .NET/C# 在代码中测量代码执行耗时的建议（比较系统性能计数器和系统时间）...