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

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

🌏引言

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

🎄二叉树遍历

🐱‍👤题目描述:

编一个程序,读入用户输入的一串先序遍历字符串,根据此字符串建立一个二叉树(以指针方式存储)。 例如如下的先序遍历字符串: ABC##DE#G##F### 其中“#”表示的是空格,空格字符代表空树。建立起此二叉树以后,再对二叉树进行中序遍历,输出遍历结果。

📌输入描述:

输入包括1行字符串,长度不超过100。

📌输出描述:

可能有多组测试数据,对于每组数据, 输出将输入字符串建立二叉树后中序遍历的序列,每个字符后面都有一个空格。 每个输出结果占一行。

🐱‍🐉示例:

输入: abc##de#g##f###
输出:c b e g d f a

🐱‍👓思路解析:

首先我们先来看一下示例输入的二叉树的形状
【数据结构】 二叉树面试题讲解->贰,数据结构,数据结构,java,二叉树,面试题
我们首先需要做的是创建一个二叉树类,用于建立一个新的二叉树

class TreeNode1 {
    char val;
    TreeNode1 left;
    TreeNode1 right;
    TreeNode1() {}
    TreeNode1(char val) {
        this.val = val;
    }
    TreeNode1(char val, TreeNode1 left, TreeNode1 right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

接下来我们需要

  • 依旧采用递归的思想
  • 对字符串的每一个元素进行遍历,并进行判断
  • 在遍历时,我们创建一个静态变量为size,此后每遍历一个元素,size就++
  • 若不为’#',则该结点设为根节点
  • 并且size++;
  • 然后因为是前序遍历,所以根节点后面应该是左子树,然后是右子树
  • 若为’#',则该节点为null,我们只需要size++即可
  • 最后返回该结点就好

代码实现如下:

    public static TreeNode1 creatTree(String str) {
        TreeNode1 root = null;
        if (str.charAt(i) != '#') {
            root = new TreeNode1(str.charAt(i));
            i++;
            root.left = creatTree(str);
            root.right = creatTree(str);
        } else {
            i++;
        }
        return root;
    }

然后根据题意我们还需要进行一个中序遍历,这里我就不做赘述了,又不懂的小伙伴可以去看一下博主对于【数据结构】二叉数的存储与基本操作的实现的讲解

实现如下:

public static void inorder(TreeNode1 root) {
        if (root == null) {
            return;
        }
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }
}

🐱‍🏍完整代码实现:

import java.util.Scanner;
class TreeNode1 {
    char val;
    TreeNode1 left;
    TreeNode1 right;
    TreeNode1() {}
    TreeNode1(char val) {
        this.val = val;
    }
    TreeNode1(char val, TreeNode1 left, TreeNode1 right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class Main {

    public static int i = 0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            i = 0;
            String st = in.nextLine();
            TreeNode1 root = new TreeNode1();
            root = creatTree(st);
            inorder(root);
        }
    }
    public static TreeNode1 creatTree(String str) {
        TreeNode1 root = null;
        if (str.charAt(i) != '#') {
            root = new TreeNode1(str.charAt(i));
            i++;
            root.left = creatTree(str);
            root.right = creatTree(str);
        } else {
            i++;
        }
        return root;
    }
    public static void inorder(TreeNode1 root) {
        if (root == null) {
            return;
        }
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }
}

🌳二叉树的最近公共祖先

🐱‍👤题目描述:

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

    }

🐱‍🐉示例:

📌示例一

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

📌示例二

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

🐱‍👓思路解析

本题博主提供两种解题思路

🚩思路一

我们发现:

  • 如果p,q不是根节点,且p,q一个在左子树被找到,一个在右子树被找到
  • 那么该根节点为最近公共祖先
  • 【数据结构】 二叉树面试题讲解->贰,数据结构,数据结构,java,二叉树,面试题
  • 若该根节点为p或者q,那么自身则为最近祖先
    【数据结构】 二叉树面试题讲解->贰,数据结构,数据结构,java,二叉树,面试题
    若最后都没有找到,说明没有,返回空

🚩思路二

我们建立两个栈:

  • 栈1用于存储找到p结点的路径
  • 栈2用于存储找到q结点的路径
    【数据结构】 二叉树面试题讲解->贰,数据结构,数据结构,java,二叉树,面试题
  • 然后我们对两个栈求长度,把栈长度比较长的栈进行出栈,直到两个栈长度相等
  • 然后同时出栈进行一一比对,相同则为p、q的最近公共祖先
    【数据结构】 二叉树面试题讲解->贰,数据结构,数据结构,java,二叉树,面试题
    这种思路的解题难点在于如何找到p、q的路径并放入栈中,博主采用的做法如下:
  • 首先我们对二叉树与所找p、q结点进行判断
  • 若为空返回false
  • 然后我们需要对当前根节点进行判断,若为我们要找的p或q
  • 则返回true
  • 若没有我们便对该根节点的左子树进行入栈并进行判断,若找到返回true
  • 若没有找到则将该左子树进行出栈
  • 然后对右子树进行同样操作
  • 最后若都没找到,返回false

然后我们只需要对两栈元素进行出栈进行比对就好了,最先相等的就为我们的最近公共祖先

🐱‍🏍代码实现:

🎈思路一代码实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(p == root || q == root) {
            return root;
        }
        if(root == null) {
            return null;
        }
        TreeNode l = lowestCommonAncestor(root.left,p,q);
        TreeNode r = lowestCommonAncestor(root.right,p,q);
        if(l != null && r != null) {
            return root;
        } else if(l != null) {
            return l;
        } else if(r != null) {
            return r;
        }
        return null;
    }
}

🎈思路二代码实现

class Solution {
        public boolean getPath(TreeNode root, TreeNode node,
                           Deque<TreeNode> stack) {
        if(root == null || node == null)return false;
        stack.push(root);
        //放完之后 要检查
        if(root == node) return true;
        boolean ret1 = getPath(root.left,node,stack);
        if(ret1) return true;
        boolean ret2 = getPath(root.right,node,stack);
        if(ret2) return true;
        stack.pop();
        return false;
    }
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        //1、两个栈当中 存储好数据
        Deque<TreeNode> stack1 = new LinkedList<>();
        getPath(root,p,stack1);
        Deque<TreeNode> stack2 = new LinkedList<>();
        getPath(root,q,stack2);
        //2、判断栈的大小
        int size1 = stack1.size();
        int size2 = stack2.size();
        if(size1 > size2) {
            int size = size1-size2;
            while (size != 0) {
                stack1.pop();
                size--;
            }
        }else {
            int size = size2-size1;
            while (size != 0) {
                stack2.pop();
                size--;
            }
        }
        //栈里面数据的个数 是一样的
        while (!stack1.isEmpty() && !stack2.isEmpty()) {
            if(stack1.peek() != stack2.peek()) {
                stack1.pop();
                stack2.pop();
            }else {
                return stack1.peek();
            }
        }
        return null;
    }
}

🎍从前序与中序遍历序列构造二叉树

🐱‍👤题目描述

给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。

/**
 * 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 buildTree(int[] preorder, int[] inorder) {

    }
}

🐱‍🐉示例:

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

🐱‍👓思路解析:

我们知道前序遍历里面第一个存储的是我们的根节点

那我们就可以在我们中序遍历中找到该结点,则该结点两边就为该根节点的左右子树
对于任意一颗树而言,前序遍历的形式总是

[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]

即根节点总是前序遍历中的第一个节点。而中序遍历的形式总是

[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]

只要我们在中序遍历中定位到根节点,那么我们就可以分别知道左子树和右子树中的节点数目。由于同一颗子树的前序遍历和中序遍历的长度显然是相同的,因此我们就可以对应到前序遍历的结果中,对上述形式中的所有左右括号进行定位。

这样以来,我们就知道了左子树的前序遍历和中序遍历结果,以及右子树的前序遍历和中序遍历结果,我们就可以递归地对构造出左子树和右子树,再将这两颗子树接到根节点的左右位置。

我们的做法是这样的

  • 我们对前序遍历结果进行下标利用下标 i 遍历,并放入到二叉树中

  • 【数据结构】 二叉树面试题讲解->贰,数据结构,数据结构,java,二叉树,面试题

  • 对中序遍历的元素设两个下标,一个记录最左边,一个记录最右边

  • 【数据结构】 二叉树面试题讲解->贰,数据结构,数据结构,java,二叉树,面试题

  • 对前序遍历里的每一个元素我们会在中序遍历里进行查找,找到后

  • 我们的inbegin与inend在左右子树里又会有新的指向

  • 【数据结构】 二叉树面试题讲解->贰,数据结构,数据结构,java,二叉树,面试题

  • 然后我们利用递归的思想,对所有元素进行遍历

  • 结束条件为inend < inbengin

  • 【数据结构】 二叉树面试题讲解->贰,数据结构,数据结构,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 int i = 0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {

        return buildTreeChild(preorder,inorder,0,inorder.length-1);
    }

    public TreeNode buildTreeChild(int[] preorder, int[] inorder,
    int inbegin,int inend) {
        if(inbegin > inend) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[i]);
        //找到当前根,在中序遍历的位置
        int rootIndex = findIndex(inorder,inbegin,inend,preorder[i]);
        i++;
        root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);
        root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);
        return root;
    }

    private int findIndex( int[] inorder,int inbegin,int inend, int key) {
        for(int i = inbegin;i <= inend; i++) {
            if(inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }
}

🌲拓展——从中序与后序遍历序列构造二叉树

与从前序与中序遍历序列构造二叉树实现类似,这里不再做过多赘述

代码实现:

    class Solution2 {
        public int i = 0;
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            i = postorder.length-1;
            return buildTreeChild(postorder,inorder,0,inorder.length-1);
        }

        public TreeNode buildTreeChild(int[] postorder, int[] inorder,
                                       int inbegin,int inend) {
            if(inbegin > inend) {
                return null;
            }
            TreeNode root = new TreeNode(postorder[i]);
            //找到当前根,在中序遍历的位置
            int rootIndex = findIndex(inorder,inbegin,inend,postorder[i]);
            i--;
            root.right = buildTreeChild(postorder,inorder,rootIndex+1,inend);
            root.left = buildTreeChild(postorder,inorder,inbegin,rootIndex-1);
            return root;
        }

        private int findIndex( int[] inorder,int inbegin,int inend, int key) {
            for(int i = inbegin;i <= inend; i++) {
                if(inorder[i] == key) {
                    return i;
                }
            }
            return -1;
        }
    }

⭕总结

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

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

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

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

相关文章

  • 【数据结构】二叉树算法讲解(定义+算法原理+源码)

    博主介绍:✌全网粉丝喜爱+、前后端领域优质创作者、本质互联网精神、坚持优质作品共享、掘金/腾讯云/阿里云等平台优质作者、擅长前后端项目开发和毕业项目实战✌有需要可以联系作者我哦! 🍅附上相关C语言版源码讲解🍅 👇🏻 精彩专栏推荐订阅👇🏻 不然下次找

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

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

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

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

    2024年02月07日
    浏览(39)
  • 数据结构与算法分析 第五章 树和二叉树 作业讲解

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

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

    封建迷信我嗤之以鼻,财神殿前我长跪不起 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)
  • 数据结构进阶篇 之 【二叉树顺序存储(堆)】的整体实现讲解(赋完整实现代码)

    做人要谦虚,多听听别人的意见,然后记录下来,看看谁对你有意见 3.1 向下调整算法 AdJustDown 3.2 向上调整算法 AdJustUP 3.3 堆的创建 3.3.1 向上建堆 3.3.2 向下建堆 3.3.3 堆的初始化与销毁 3.3.4 堆的插入(压栈) 3.3.5 取堆顶的数据 3.3.6 堆的删除 3.3.7 堆的数据个数 3.3.8 堆的判空

    2024年04月17日
    浏览(72)
  • 【Java 数据结构】二叉树

    树是一种 非线性 的数据结构,它是由n(n=0)个有限结点组成一个具有层次关系的集合。 把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的 。 有一个特殊的结点,称为根结点,根结点没有前驱结点 除根结点外,其余结点被分成M(M 0)个互不相交的

    2024年02月20日
    浏览(45)
  • 【java数据结构-二叉树(上)】

    🔥个人主页: 努力学编程’ 🔥内容管理: java数据结构 hello,今天带大家学习 数据结构 中非常重要的一个知识点 二叉树 ,二叉树主体的实现使用的是递归的知识,通过二叉树我们可以更好的理解递归的应用。今天就带大家学习一下二叉树的一些知识。 概念 : 树是一种非

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

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

    2024年02月08日
    浏览(41)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包