树的一些经典 Oj题 讲解

这篇具有很好参考价值的文章主要介绍了树的一些经典 Oj题 讲解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

关于树的遍历

先序遍历

我们知道 树的遍历有 前序遍历 中序遍历 后序遍历 然后我们如果用递归的方式去解决,对我们来说应该是轻而易举的吧!那我们今天要讲用迭代(非递归)实现 树的相关遍历
首先呢 我们得知道 迭代解法 本质上也是在模拟递归,因为递归的过程中使用了系统栈,所以我们在迭代的时候也要用Stack来模拟系统栈。
我们要一开始就要创建一个顺序表接收打印的值 最终程序结束输出出来。
首先我们要创建一个栈来存放结点 ,首先我们就要打印根节点的值 ,此时栈中的内容为null,所以我们优先将头结点puth进去栈,然后打印。其实就很好理解 如果树为空 直接就返回了 。

树的一些经典 Oj题 讲解,java,数据结构
我们首先从根节点开始遍历 只要节点不为空 就进入循环 就push 进栈 再打印 再去遍历左子树 ,直到左子树为空,就进不来循环 了 我们就要从栈中弹出元素,去遍历他的右子树 但是现在只有一层循环 不能够继续进入回到上面再进入左子树的循环 那怎么办呢 我们就可以再加一层循环在最外面包着他们 判断条件依然是节点不为空 ,但是这样就解决了吗 当然还没有 你去遍历右子树 肯定会最后右孩子结点为空 又怎么返回循环呢 此时已经节点为空了 进不去循环了 但是还没遍历结束, 该怎么办呢 现在栈还没空 也是一个判断条件 我们就可以再外层循环加一个条件栈不为空

最终的实现你们可以参考代码:

public List<Integer> preorderTraversal(TreeNode root) {
        //先定义一个顺序表去接收
        List<Integer> list = new ArrayList<>();
        if(root == null){
            return list;
        }

        //用链表去实现一个栈
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()){
        while(cur != null){
            list.add(cur.val);
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        cur = cur.right;
        }
        return list;
    }

根据代码去分析上面那棵二叉树 我们就可以输出他的二叉树遍历序列。

中序遍历

通过上面的先序遍历 ,我们可以知道大概的思路 。其实中序遍历迭代(非递归)实现 和先序遍历的实现其实差不太多 就输出的位置换一下 因为是 左 根 右 ,所以我们先去遍历完左子树 ,push进栈。 左子树为空 的时候再从栈中弹出元素 打印元素。
具体代码实现如下:

 public List<Integer> inorderTraversal(TreeNode root) {
 //先定义一个顺序表去接收
        List<Integer> list = new ArrayList<>();
        if(root == null){
            return list;
        }

        //用链表去实现一个栈
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()){
        while(cur != null){
            
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        list.add(cur.val);
        cur = cur.right;
        }
        return list;
    }

写到这里 大家是不是觉得 so easy 后序遍历 想直接开敲 ,但是这里提醒大家 后序遍历 没有前序和中序那样简单了 后序会涉及到一个记录结点。 下面我们来分析一下

后序遍历

大体思路和前面两种一样 还是利用栈来实现 因为 后序遍历是 左 右 根
树的一些经典 Oj题 讲解,java,数据结构
首先我们先用cur遍历左子树,只要左子树不为空 , 就push进栈 如果左子树为空的话 怎么办呢 ? 我们要从栈中弹出元素吗 那肯定不行啊 因为你还得判断后面有没有右子树 ,所以你只能peek出来看一下。 如果有右子树 我们则让cur = peek出来的节点的右子树,如果右子树为空呢 我们是不是可以pop出栈并且打印出来 。然后现在cur是为空的 进不去循环 然后我们又peek一下栈顶元素 判断他右子树为不为空 但是你会发现现在代码死循环了 他还是会打印刚才的打印过的节点的值 那怎么办呢 ? 很简单 我们定义一个节点prev 来记录一下打印过的结点 。只要peek出来的元素的右孩子 是prev 说明打印过 就直接将他弹出来 打印 所以 现在我们有两个条件可以直接弹出来 打印 然后记录一下, 就是当右孩子为空 或者右孩子是已经打印过的结点 就可以弹出栈顶的元素打印 因为该元素已经是最后一次用了 。
下面我们直接上代码:

 public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null){
            return list;
        }
        //创建一个栈
        Stack<TreeNode> stack = new Stack<>();
        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();
                list.add(top.val);
                prev = top;
            }else{
                cur = top.right;
            }
        }
        return list;
    }

二叉树转字符串

题目是这样描述的 给你二叉树的根节点 root ,请你采用前序遍历的方式,将二叉树转化为一个由括号和整数组成的字符串,返回构造成的字符串。

空节点 用一对空括号“()”表示,转化后可以省略所有不影响字符串与原始的二叉树直接的一对一关系的空括号对。

相信大家读完题目会觉得很懵 ,其实题目的情况分为4种 :
1.左右子树都有 则需要 这样加括号:root((left),(right));
2、只有右子树 :root((), (right));
3、只有左子树:root((right));
4、叶子节点 :root;

总的来说 不管有没有左子树 ,只要有右子树 左子树都要加括号。
下面来看几个示例:
树的一些经典 Oj题 讲解,java,数据结构
树的一些经典 Oj题 讲解,java,数据结构
树的一些经典 Oj题 讲解,java,数据结构
看完示例 相信大家已经知道思路了 我们直接上代码:

 StringBuilder sb = new StringBuilder();
    public String tree2str(TreeNode root) {
        preoderTraveral(root);
        return sb.toString();
    }
    private void preoderTraveral(TreeNode root){
        if(root == null){
            return;
        }
        sb.append(root.val);
        if(root.left != null || root.right != null){
            sb.append("(");
            preoderTraveral(root.left);
            sb.append(")");
            if(root.right != null){
                sb.append("(");
                preoderTraveral(root.right);
                sb.append(")");
            }
        }
    }

看完上面四道题目 相信大家已经想去跃跃欲试了 下面我把题目的链接放在下面

迭代实现前序遍历

迭代实现中序遍历

迭代实现后序遍历

根据二叉树创建字符串

其实关于树的OJ题有很多 感兴趣的可以去力扣或者牛客网上 查找做一下 。

最后感谢大家的浏览 !!!文章来源地址https://www.toymoban.com/news/detail-810891.html

到了这里,关于树的一些经典 Oj题 讲解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【数据结构与算法】:10道链表经典OJ

    思路1:遍历原链表,将 val 所在的节点释放掉。(太麻烦) 思路2:创建新链表,再遍历原链表,找到不为 val 的节点尾插到新链表。 思路1代码实现如下: 注意: 1.当链表为空时,直接返回NULL即可。 2.当尾插上最后一个有效节点时,此时它的 next 可能还与最后一个节点相链接,

    2024年04月14日
    浏览(39)
  • 【数据结构】链表经典OJ题,常见几类题型(二)

    看到这类题型首先要判断链表是否相交,而相交条件: 两链尾部节点相同(地址相同, val 值相同, next 相同) 。这样我们便可 找到两链表的尾节点并判断这两个节点地址是否相同 ,若相同则两链表相交。上面这种情况两链表呈 \\\'Y\\\' 型,那么我们想一下两链表相交是否可以

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

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

    2024年02月07日
    浏览(44)
  • 【数据结构与算法】二叉树的知识讲解

    目录  一,二叉树的结构深入认识  二,二叉树的遍历  三,二叉树的基本运算 3-1,计算二叉树的大小 3-2,统计二叉树叶子结点个数 3-3,计算第k层的节点个数 3-4,查找指定值的结点         二叉树是不可随机访问的,二叉树的结构是通过双亲结点与孩子结点之间的连接进

    2024年02月08日
    浏览(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日
    浏览(65)
  • 数据结构刷题篇 之 【力扣二叉树基础OJ】详细讲解(含每道题链接及递归图解)

    有没有一起拼用银行卡的,取钱的时候我用,存钱的时候你用 难度等级:⭐ 直达链接:相同的树 难度等级:⭐ 直达链接:单值二叉树 难度等级:⭐⭐ 直达链接:对称二叉树 难度等级:⭐⭐⭐ 直达链接:二叉树的前序遍历 难度等级:⭐⭐⭐⭐ 直达链接:另一颗子树 注:

    2024年04月16日
    浏览(80)
  • 【Java 数据结构】队列与OJ题

    篮球哥温馨提示:编程的同时不要忘记锻炼哦! 目录 1、什么是队列?  2、初识Queue 2.1 认识一下Queue 2.2 简单使用下Queue 3、模拟实现Queue 3.1 构造方法和成员属性 3.2 offer 方法 3.3 poll 方法 3.4  peek 方法 4、队列相关的OJ题 4.1 设计循环队列 (来源:LeetCode 难度:中等)   4.2 用队列

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

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

    2024年02月08日
    浏览(44)
  • 【Java数据结构 -- 队列:队列有关面试oj算法题】

    只允许在一端进行插入数据操作,在另一端进行删除数据操作得特殊线性表,队列是 先进先出 ,入队:进行插入操作得一端称为 队尾(rear) ,出队:进行删除操作的一端称为 队头(front) 。队列Queue是个接口, 底层通过链表实现的 。 boolean offer(E e) – 入队列 E poll() – 出队

    2024年01月25日
    浏览(48)
  • 【数据结构】超详细讲解:算术表达式转化为后缀表达式、前缀表达式、表达式树的构建

    作者: 努力学习的大一在校计算机专业学生,热爱学习和创作。目前在学习和分享:算法、数据结构、Java等相关知识。 博主主页: @是瑶瑶子啦 所属专栏: 【数据结构】:该专栏专注于数据结构知识,持续更新,每一篇内容优质,浅显易懂,不失深度! 近期目标: 写好专栏

    2024年02月08日
    浏览(53)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包