【数据结构(八)下】二叉树经典习题

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

❣博主主页: 33的博客❣
▶文章专栏分类: Java从入门到精通◀
🚚我的代码仓库: 33的代码仓库🚚
🫵🫵🫵关注我带你学更多数据结构的知识

【数据结构(八)下】二叉树经典习题,数据结构,数据结构,二叉树

1.前言

在上一篇文章中,博主已经分享了部分二叉树的经典习题,在这篇文章中,博主将继续和大家分享二叉树的经典习题。

2.二叉树经典习题

2.1公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先:OJ链接
解题思路

1.如果p,q分居在左子树和右子树,那么根节点root就是公共祖先
2.如果p,q在同一侧,若p是root,则返回p否则返回q
3.如果p,q在同一侧,但分居在一棵树的两侧,那么parent为公共祖先。

 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root==null){
            return null;
        }
        if(p==root||q==root){
            return root;
        }
        //P、Q都不为root且不为空
        TreeNode Left=lowestCommonAncestor(root.left,p,q);
        TreeNode Right =lowestCommonAncestor(root.right,p,q);
        if(Left!=null&&Right!=null){
            return root;
        }
        //Left与Rihet在一边
        if (Left!=null){
            return Left;
        }
        else{
            //Right!=null或者Left==null&&Rightnull
            return Right;
        }     
    }

栈实现

public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
    Stack<TreeNode> stackp=new Stack<>();
    Stack<TreeNode> stackq=new Stack<>();
    getpath(root,p,stackp);
    getpath(root,q,stackq);
    int sizep= stackp.size();
    int sizeq=stackq.size();
    int size=sizep-sizeq;
    if (size>0){
        while (size!=0){
            stackp.pop();
            size--;
        }
    }else {
        while (size!=0){
            stackq.pop();
            size--;
        }
    }
    while (!stackp.isEmpty()&&!stackq.isEmpty()){
        TreeNode curp=stackp.pop();
        TreeNode curq=stackq.pop();
        if(curp.equals(curq)){
            return curp;
        }
    }
    return null;
    }
    public  Boolean getpath(TreeNode root, TreeNode node, Stack<TreeNode> stack){
        if(root==null||node==null){
            return false;
        }
        stack.push(root);
        if (root==node){
            return true;
        }
        boolean Left=getpath(root.left,node,stack);
        if (Left==true){
            return true;
        }
        boolean Right=getpath(root.right,node,stack);
        if (Right==true){
            return true;
        }
        stack.pop();
        return false;
    }

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

给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树:OJ链接
解题思路

1.根据前序遍历在中序遍历中找到根节点
2.中序遍历中,根的左边为左子树,根的右边为右子树
3.在根据前序遍历在中序中找到根节点,直到end的大于begin的左边

public TreeNode buildTree(int[] preorder, int[] inorder) {

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

    }
    public int i=0;
    public TreeNode buildTreeChild(int[] preorder, int[] inorder,int ib,int ie){
        if(ib>ie){
            return null;
        }
        TreeNode root=new TreeNode(preorder[i]);
        int index=Find(preorder[i],inorder,ib,ie);
        if (index==-1){
            return null;
        }
        i++;
        root.left=buildTreeChild(preorder, inorder, ib, index-1);
        root.right=buildTreeChild(preorder, inorder, index+1, ie);
        return root;
    }
    public int Find(int a,int[] arr,int ib,int ie){
        for (int j=ib;j<=ie;j++){
            if(arr[j]==a){
                return j;
            }
        }
       return -1;
    }

2.3后序与中序遍历序列构造二叉树

后序与中序遍历序列构造二叉树:OJ链接

int post;
    public TreeNode buildTree2(int[] inorder, int[] postorder) {
        post=postorder.length-1;
        return buildTreeChild2(inorder,postorder,0,inorder.length-1);
    }
    public TreeNode buildTreeChild2(int[] inorder, int[] postorder,int ib,int ie) {

        if(ib>ie){
            return null;
        }
        TreeNode root=new TreeNode(postorder[post]);
        int index=Find(postorder[post],inorder,ib,ie);
        if (index==-1){
            return null;
        }
        post--;
        root.right=buildTreeChild2(inorder,postorder,index+1,ie);
        root.left=buildTreeChild2(inorder,postorder,ib,index-1);
        return root;
    }

2.4二叉树创建字符串

给你二叉树的根节点 root ,请你采用前序遍历的方式,将二叉树转化为一个由括号和整数组成的字符串:OJ链接
解题思路

1.先遍历左边,如果左子树不为空:+(+左子树+),如果左子树为空:判断右子树是否为空,如果不为空+()
2.遍历右子树,如果右子树不为空:+(+左子树+),如果右子树为空return

public String tree2str(TreeNode root) {
        StringBuilder stringBuilder =new StringBuilder();
        tree2str(root,stringBuilder);
        return stringBuilder.toString();
    }
    public void tree2str(TreeNode root,StringBuilder stringBuilder) {
        if(root==null){
            return ;
        }
        stringBuilder.append(root.val);
        if(root.left!=null){
            stringBuilder.append("(");
            tree2str(root.left,stringBuilder);
            stringBuilder.append(")");
        }else {
            //root.left==null
            if(root.right!=null){
                stringBuilder.append("()");
            }else {
               //root.left==null &&root.left==null
                return ;
            }
        }
        if(root.right!=null){
            stringBuilder.append("(");
            tree2str(root.right,stringBuilder);
            stringBuilder.append(")");
        }else {
            //root.right==null
            return;
        }
    }

2.5非递归前序遍历

解题思路

1.用栈来实现
2.前序遍历是根左右,我们先让根节点入栈.再一直向左遍历,当为空的时候就返回遍历右节点,如果右节点也为空,那么就出栈.

void preorder(TreeNode root){
        Stack<TreeNode> stack=new Stack<>();
        if(root==null){
            return;
        }
        TreeNode cur=root;
        while (cur!=null||!stack.isEmpty()){
            while (cur!=null){
                stack.push(cur);
                System.out.println(cur.val+" ");
                cur=cur.left;
            }
            TreeNode top=stack.pop();
            cur=top.right;
        }

    }

2.6非递归中序遍历

解题思路

整体思路和前序遍历相似
1.用栈来实现
2.中序遍历是左根右,我们先让左节点入栈.再一直向左遍历,当为空的时候就出栈,返回父节点,再遍历右节点,如果右节点也为空,那么继续出栈.

void inorder(TreeNode root){
        Stack<TreeNode> stack=new Stack<>();
        if(root==null){
            return;
        }
        TreeNode cur=root;
        while (cur!=null||!stack.isEmpty()){
            while (cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            TreeNode top=stack.pop();
            System.out.println(top.val+" ");
            cur=top.right;
        }

    }

2.7非递归后序遍历

解题思路

整体思路和前序遍历相似
1.用栈来实现
2.中序遍历是左右根,我们先让左节点入栈.再一直向左遍历,当为空的时候需要判断右节点是否为空,如果右节点为空则出栈,如果右节点不为空那么遍历右节点.
3.但是我们需要注意的是:当右节点不为空遍历右节点的时候,可能造成死循环,所以我们需要定义一个值来表示最后一个被打印的节点。

 void postorder(TreeNode root) {
        Stack<TreeNode> stack=new Stack<>();
        if(root==null){
            return;
        }
        TreeNode cur=root;
        TreeNode prev=null;
        while (cur!=null||!stack.isEmpty()){
            while (cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            TreeNode top=stack.peek();{
                if (top.right==null||top.right==prev){
                    stack.pop();
                    System.out.println(top.val+" ");
                    prev=top;//标记被打印的节点
                }else {
                    cur=top.right;
                }
            }
        }
    }

3.总结

博主整理的只是一部分二叉树的习题,在二叉树中,还有很多有趣的习题没和大家分享,感兴趣的同学可以自己去练习。

下期预告:优先级队列文章来源地址https://www.toymoban.com/news/detail-859359.html

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

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

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

相关文章

  • 【数据结构】——树和二叉树的相关习题

    1、设高度为h的二叉树上只有度为0和度为2的结点,则该二叉树中所包含的结点数至少为(),最多为()。 A、h ;2 h -1 B、2h-1 ; 2 h -1 C、2h+1; 2 h-1 -1 D、h+1;2 h -1 解析: (B) 最少的情况下,除了根结点该层为1个结点以外,其余h-1层都有2个结点,得2(h-1),即2(h-1)+1=2h-1。

    2024年02月03日
    浏览(44)
  • 【数据结构与算法】树和二叉树课后习题

    知一棵树边的集合为 I , M , I , N , E , I , B , E , B , D , A , B , G , J , G , K , C , G , C , F , H , L , C , H , A , C {I,M,I,N,E,I,B,E,B,D,A,B,G,J, G,K,C,G,C,F,H,L,C,H,A,C} I , M , I , N , E , I , B , E , B , D , A , B , G , J , G , K , C , G , C , F , H , L , C , H , A , C 请画出这棵树并回答下列问题: 哪个是根结点? 哪些是叶

    2024年02月12日
    浏览(38)
  • 数据结构:二叉树经典例题(单选题)-->你真的掌握二叉树了吗?(第二弹)

     朋友们、伙计们,我们又见面了,本期来给大家解读一下有关二叉树的经典例题,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! C 语 言 专 栏: C语言:从入门到精通 数据结构专栏: 数据结构 个  人  主  页 : stackY、 ​ 目录   前言: 一、

    2024年02月10日
    浏览(88)
  • 数据结构:二叉树经典例题(单选题)-->你真的掌握二叉树了吗?(第一弹)

    朋友们、伙计们,我们又见面了,本期来给大家解读一下有关二叉树的经典例题,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! C 语 言 专 栏: C语言:从入门到精通 数据结构专栏: 数据结构 个  人  主  页 : stackY、 目录 前言: 一、 二、

    2024年02月10日
    浏览(40)
  • 【数据结构入门指南】二叉树顺序结构: 堆及实现(全程配图,非常经典)

    普通的二叉树是不适合用数组来存储的,因为可能会存在大量的空间浪费。 而完全二叉树更适合使用顺序结构存储。   现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储 ,需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事,一个是数据结构,一

    2024年02月12日
    浏览(39)
  • 【数据结构入门指南】二叉树链式结构的实现(保姆级代码思路解读,非常经典)

    其他数据结构不同,二叉树的增删查改接口实现的意义不大(后续搜索树的增删查改才有意义)。普通初阶二叉树更重要的是学习控制结构,为后续的AVL树、红黑树等高级数据结构打下基础。同时大部分OJ题也出在此处。 所谓二叉树遍历(Traversal)是按照某种特定的规则,依次

    2024年02月11日
    浏览(47)
  • 【数据结构-二叉树】二叉树

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月07日
    浏览(48)
  • 数据结构:搜索二叉树 | 平衡二叉树

    博客写的代码都放在这里:gitee仓库链接 1.二叉搜索树 1.1.基本概念 二叉搜索树又称二叉排序树, 可以为空,如果不为空具有以下性质的二叉树 : 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值 若它的右子树不为空,则右子树上所有节点的值都大于根节点的

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

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

    2024年01月25日
    浏览(63)
  • 【数据结构(四)】链表经典练习题

    ❣博主主页: 33的博客❣ ▶️文章专栏分类:数据结构◀️ 🚚我的代码仓库: 33的代码仓库🚚 🫵🫵🫵 关注我带你学更多数据结构知识 在上一篇文章中博主已经介绍了链表的基础知识,什么是链表,如何实现一个链表,以及LinkedList的操作方法,那么在这篇文章中通过一些链

    2024年04月22日
    浏览(45)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包