【数据结构】 二叉树面试题讲解->壹

这篇具有很好参考价值的文章主要介绍了【数据结构】 二叉树面试题讲解->壹。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

🌏引言

二叉树的操作算法是笔试面试中较为常见的题目。
本文将着重介绍平时面试中常见的关于二叉树的应用题目,马上要进行秋招了。希望对你们有帮助 _😀
【数据结构】 二叉树面试题讲解->壹,数据结构,数据结构,算法,java,二叉树

🍀相同的树

🐱‍🐉题目描述:

给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。

/**
 * 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) {

    }
}

🐱‍👓示例:

📌示例一

【数据结构】 二叉树面试题讲解->壹,数据结构,数据结构,算法,java,二叉树

📌示例二

【数据结构】 二叉树面试题讲解->壹,数据结构,数据结构,算法,java,二叉树

📌示例三

【数据结构】 二叉树面试题讲解->壹,数据结构,数据结构,算法,java,二叉树

🐱‍👤题目解析

这道题我们利用递归的思想,遍历两棵树的每一个结点,分别对两棵树相对应结点进行判断

对于结点的判断我们有如下几个情况

  • 有一个结点为null,这时候直接返回false;
  • 两个结点都为null,这时候直接返回true;
  • 都不为空时进行判断,若不等返回false;

整体思想,若两棵树左子树与右子树全部相等就返回true

🚩代码实现:

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

🌳另一棵树的子树

🐱‍👤题目描述:

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在,返回 true ;否则,返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

/**
 * 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 isSubtree(TreeNode root, TreeNode subRoot) {

    }
}

🐱‍🐉示例:

📌示例一

【数据结构】 二叉树面试题讲解->壹,数据结构,数据结构,算法,java,二叉树

📌示例二

【数据结构】 二叉树面试题讲解->壹,数据结构,数据结构,算法,java,二叉树

🐱‍👓解法思路:

其实这道题与上一题的解法思路类似

我们只需要传入相应的头节点与子树进行对比看看是否为同一棵树就好

只要存在就返回true

【数据结构】 二叉树面试题讲解->壹,数据结构,数据结构,算法,java,二叉树

🐱‍🐉代码实现

/**
 * 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 isSubtree(TreeNode root, TreeNode subRoot) {
        if(root == null || subRoot == null) {
            return false;
        }
        //相同树
        if(isSameTree(root,subRoot)) {
            return true;
        }
        //含子树
        return isSubtree(root.left,subRoot)||isSubtree(root.right,subRoot);
    }
    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);
    }
}

🎍翻转二叉树

🐱‍👤题目描述:

给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。

/**
 * 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) {

    }
}

🐱‍👓示例:

【数据结构】 二叉树面试题讲解->壹,数据结构,数据结构,算法,java,二叉树

🐱‍🐉思路解析:

依旧利用递归的思想,把一个大树看成许多小树

我们只需要把每一个根节点的左子树和右子树进行交换就好
【数据结构】 二叉树面试题讲解->壹,数据结构,数据结构,算法,java,二叉树

🐱‍🏍代码实现

/**
 * 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;
        }
        TreeNode tep = root.left;
        root.left = root.right;
        root.right = tep;
        
        invertTree(root.left);
        invertTree(root.right);

        return root;
    }
}

🎄平衡二叉树

🐱‍👤题目描述

给定一个二叉树,判断它是否是高度平衡的二叉树。

本题中,一棵高度平衡二叉树定义为:

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

🐱‍🐉示例:

📌示例一

【数据结构】 二叉树面试题讲解->壹,数据结构,数据结构,算法,java,二叉树

📌示例二

【数据结构】 二叉树面试题讲解->壹,数据结构,数据结构,算法,java,二叉树

📌示例三

【数据结构】 二叉树面试题讲解->壹,数据结构,数据结构,算法,java,二叉树

🐱‍👓思路解析:

🎈思路一

自顶向下,具体做法类似于二叉树的前序遍历,即对于当前遍历到的节点,首先计算左右子树的高度,如果左右子树的高度差是否不超过 111,再分别递归地遍历左右子节点,并判断左子树和右子树是否平衡。这是一个自顶向下的递归的过程。

利用递归思想进行逐个遍历,但是这时候的时间复杂度较高,为O(N^2);

🎈思路二

自底向上,自底向上递归的做法类似于后序遍历,对于当前遍历到的节点,先递归地判断其左右子树是否平衡,再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的,则返回其高度(高度一定是非负整数),否则返回 −1。如果存在一棵子树不平衡,则整个二叉树一定不平衡。

然后返回即可,此时的时间复杂度为O(N)

🐱‍🏍代码实现

🚩思路一实现:

/**
 * 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 isBalanced(TreeNode root) {
        if(root == null) {
            return true;
        } 
        int l = maxDepth(root.left);
        int r = maxDepth(root.right);
        return Math.abs(l - r) < 2 && isBalanced(root.left) &&isBalanced(root.right);
    }
        public int maxDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int leftHeight = maxDepth(root.left);
        int rightHeight = maxDepth(root.right);

        return (leftHeight > rightHeight) ?
                (leftHeight+1):(rightHeight+1);
    }

}

🚩思路二实现:

class Solution {
    public boolean isBalanced(TreeNode root) {
        return height(root) >= 0;
    }

    public int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        } else {
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }
}

🌲对称二叉树

🐱‍👤题目描述

给你一个二叉树的根节点 root , 检查它是否轴对称。

/**
 * 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 isSymmetric(TreeNode root) {
   
    }
}

🐱‍👓示例:

📌示例一

【数据结构】 二叉树面试题讲解->壹,数据结构,数据结构,算法,java,二叉树

📌示例二

【数据结构】 二叉树面试题讲解->壹,数据结构,数据结构,算法,java,二叉树

🐱‍🐉思路解析

如果一个树的左子树与右子树镜像对称,那么这个树是对称的。

因此,该问题可以转化为:两个树在什么情况下互为镜像?

如果同时满足下面的条件,两个树互为镜像:

  • 它们的两个根结点具有相同的值

  • 每个树的右子树都与另一个树的左子树镜像对称

🐱‍🏍代码实现:

/**
 * 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 isSymmetric(TreeNode root) {
        return issymmetric(root.left,root.right);
    }
    public boolean issymmetric(TreeNode l,TreeNode r) {
        if(l != null&&r == null || l == null && r != null) {
            return false;
        }
        if(l == null && r == null ) {
            return true;
        }
        if(l.val != r.val ) {
            return false;
        }
        return issymmetric(l.left,r.right) && issymmetric(l.right,r.left);
    }
}

🎡二叉树的层序遍历

🐱‍👤题目描述:

给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。

/**
 * 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 List<List<Integer>> levelOrder(TreeNode root) {

    }
}

🐱‍🐉示例:

【数据结构】 二叉树面试题讲解->壹,数据结构,数据结构,算法,java,二叉树

🐱‍👓思路解析:

我们创建一个队列,用于储存每一层二叉树的结点,每一次当我们将头元素进行出队后,我们又会将下一层的结点进行入队,然后依次进行遍历,直到队列为null则结束循环

【数据结构】 二叉树面试题讲解->壹,数据结构,数据结构,算法,java,二叉树

先将根节点root进入到该队列,创建一个list顺序表里面的元素也为顺序表,每一个元素用于储存每一层的结点

此后会在一个while循环里对该二叉树进行遍历,结束循环的条件为队列为空,
做法为

  • 我们每一次循环都会求一次队列的长度
  • 创建一个顺序表tmp进行储存该层结点
  • 在循环里再来一个循环,目的是:
  • 把当前队列里存储的结点出队到tmp里面进行存储
  • 把下一层二叉树的结点进行入队
  • 该内while循环结束后tmp里面储存的就是该层的二叉树的所有元素
  • 此时再将tmp添加到list顺序表里即可
  • 此时第一层二叉树遍历完毕,队列不为空
  • 继续执行外层循环

🐱‍🏍代码实现:

/**
 * 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 List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if(root == null) {
            return list;
        }
        queue.offer(root);
        TreeNode cur = root;
        while(!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> tmp = new ArrayList<>();
            while(size != 0) {
                cur = queue.poll();
                tmp.add(cur.val);
                size--;
                if(cur.left != null) {
                    queue.offer(cur.left);
                }
                if(cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            list.add(tmp);
        }
        return list;
    }
}

⭕总结

关于《【数据结构】 二叉树面试题讲解->壹》就讲解到这儿,感谢大家的支持,欢迎各位留言交流以及批评指正,如果文章对您有帮助或者觉得作者写的还不错可以点一下关注,点赞,收藏支持一下!文章来源地址https://www.toymoban.com/news/detail-692051.html

到了这里,关于【数据结构】 二叉树面试题讲解->壹的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构与算法分析 第五章 树和二叉树 作业讲解

     参考教材: 《数据结构(C语言版 第2版)》 严蔚敏,李冬梅,吴伟民编著,人民邮电出版社,2022年版。 截图未标明出处均为原创或取自《数据结构(C语言版 第2版)》~   本文对应的作业题讲解视频:   数据结构与算法分析作业讲解视频合集 https://www.bilibili.com/video/BV1N

    2024年02月02日
    浏览(37)
  • 【算法与数据结构】二叉树的三种遍历代码实现(上)—— 用递归序知识点讲解

      本篇博客 (上篇) 先带大家学习 递归方式 进行三种遍历, 而在后续的 (下篇) 中将为大家详细讲解非递归的三种遍历方式。 目录 1、二叉树 2、二叉树的递归遍历 2.1、先序遍历 2.2、中序遍历 2.3、后序遍历  二叉树(Binary tree)是树形结构的一个重要类型。许多实际问

    2024年02月08日
    浏览(41)
  • 【数据结构】二叉树面试题

    目录 1.二叉树的最大深度 2.相同的树 3.另一棵树的子树 4.翻转二叉树 5.平衡二叉树 6.对称二叉树 7.完全二叉树 8.二叉树遍历 9.层序遍历 10.根据中序和前序序列构造二叉树 11.根据中序和后序序列构造二叉树 12.二叉树的最近公共祖先 13.非递归前序遍历 14.非递归中序遍历 15.非递

    2024年02月11日
    浏览(39)
  • 数据结构进阶篇 之 【二叉树】详细概念讲解(带你认识何为二叉树及其性质)

    有朋自远方来,必先苦其心志,劳其筋骨,饿其体肤,空乏其身,鞭数十,驱之别院 1.1 二叉树中组分构成名词概念 1.2 二叉树的结构概念 1.3 特殊的二叉树 2.1 顺序存储 2.2 链式存储 前言: 在你的想象中如果有一个“二叉树”会是什么样子呢? 顾名思义,现实中的二叉树我们

    2024年04月13日
    浏览(42)
  • 树的引进以及二叉树的基础讲解——【数据结构】

                                     W...Y的主页 😊 代码仓库分享  💕 当我们学习完前面的数据结构,难度也就会上升,但是这个也是非常重要的数据结构。今天我们来学习一种新的数据类型——树。 目录 树的概念以及结构 树的概念 树的相关概念 树的表示

    2024年02月07日
    浏览(39)
  • 【数据结构和算法】--- 二叉树(3)--二叉树链式结构的实现(1)

    在学习二叉树的基本操作前,需先要创建一棵二叉树,然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入,且为了方便后面的介绍,此处手动快速创建一棵简单的二叉树,快速进入二叉树操作学习,等二叉树结构了解的差不多时,我们反过头再来研

    2024年01月25日
    浏览(58)
  • 数据结构进阶篇 之 【二叉树链序存储】的整体实现讲解

    封建迷信我嗤之以鼻,财神殿前我长跪不起 1.1 手动创建 1.2 前序递归创建 2.1 前序,中序以及后序遍历概念 2.2 层序遍历概念 2.3 前序打印实现 2.4 中序打印实现 2.4 后序打印实现 2.5 层序打印实现 2.6 判断是否为完全二叉树 3.1 二叉树节点个数 3.2 二叉树第k层节点个数 3.3 二叉树

    2024年04月13日
    浏览(41)
  • 数据结构----完全二叉树的时间复杂度讲解,堆排序

    目录 一.建堆的时间复杂度 1.向上调整算法建堆 2.向下调整算法建堆 二.堆排序 1.概念 2.代码思路 3.代码实现 我们就以极端情况考虑时间复杂度(满二叉树+遍历所有层) 假设所有节点个数为N,树的高度为h N = 2^0+2^1+2^2......+2^(h-1) 即N = 2^h - 1 h = log(N+1) 时间复杂度我们以交换次数为

    2024年03月14日
    浏览(63)
  • 数据结构与算法-二叉树

            在计算机科学中,数据结构是组织和存储数据的基础框架,而算法则是处理这些数据的核心逻辑。在这众多的数据结构中,二叉树因其独特的层级结构、高效的搜索和插入操作,成为广泛应用的一种非线性数据结构。本文将深入探讨二叉树的定义、种类、操作方法

    2024年03月10日
    浏览(57)
  • 【数据结构与算法】—— 二叉树

    目录 一、树 1、初识树 2、树的一些概念 3、树的表示形式 二、二叉树 1、初识二叉树 2、两种特殊的二叉树 3、二叉树的性质  4、二叉树的遍历 5、实现一棵二叉树  6、二叉树题目(没代码的后面会给补上) (1)根节点没有前驱。 (2)子树的根节点只有一个前驱,可以有

    2024年04月09日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包