Java LeetCode篇-深入了解二叉树的经典解法(多种方式实现:构造二叉树)

这篇具有很好参考价值的文章主要介绍了Java LeetCode篇-深入了解二叉树的经典解法(多种方式实现:构造二叉树)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

🔥博客主页: 【小扳_-CSDN博客】
❤感谢大家点赞👍收藏⭐评论✍
   

Java LeetCode篇-深入了解二叉树的经典解法(多种方式实现:构造二叉树),Java LeetCode篇,leetcode,职场和发展,java,数据结构

Java LeetCode篇-深入了解二叉树的经典解法(多种方式实现:构造二叉树),Java LeetCode篇,leetcode,职场和发展,java,数据结构

文章目录

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

        1.1 实现从前序与中序遍历序列来构造二叉树思路   

        1.2 代码实现从前序与中序遍历序列来构造二叉树

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

        2.1 实现从中序与后序遍历序列后遭二叉树思路

        2.2 代码实现从中序与后序遍历序列来构造二叉树

        3.0 根据后缀表达式创建二叉树

        3.1 实现后缀表达式创建二叉树思路

        3.2 代码实现后缀表达式创建二叉树

         4.0 相同的树

        4.1 实现判断两颗树是否相同思路

        4.2 代码实现相同树

         5.0 另一颗树的子树

        5.1 实现判断是否为另一颗树的子树

        5.2 代码实现判断是否为另一颗树的子树


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

题目:

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

示例 1:

Java LeetCode篇-深入了解二叉树的经典解法(多种方式实现:构造二叉树),Java LeetCode篇,leetcode,职场和发展,java,数据结构

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

OJ链接:

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

        1.1 实现从前序与中序遍历序列来构造二叉树思路   

        具体思路为:前序遍历的流程先是访问根节点,到左子树,再到右子树的顺序;中序遍历的流程先是左子树,到访问根节点,再到右子树。因此,在前序的序列中的第一个元素就是该树的根节点的值,然后再通过中序的序列中遍历找根节点。接着就可以将其中序的序列进行拆分,在中序序列中根节点的值的左边部分的序列为左子树,在中序序列中根节点的值的右边部分序列为右子树。又接着将前序序列进行拆分,从索引为 1 开始,长度为:与中序序列中左子树的序列数量是一致的,将这一部分称为左子树;从索引 (1+长度)开始到该序列的结束,将这一部分称为右子树。接下来就是子问题了,通过递归,找到当前节点的左右子树。

Java LeetCode篇-深入了解二叉树的经典解法(多种方式实现:构造二叉树),Java LeetCode篇,leetcode,职场和发展,java,数据结构

       具体例子:前序序列 pre = {3,9,20,15,7},中序序列 in = {9,3,15,20,7} 。先找到该树的节点值 int rootValue = pre[0], TreeNode root = new TreeNode(rootValue),创建该树的根节点。接着对中序序列遍历来找到根节点的值,i == 1 ,在中序序列中找左右子树:在索引在该区间 [0,1)是节点的左子树,而在索引为 [2,5)区间是节点的右子树。在前序序列中找左右子树:在索引为 [1,2)是该节点的左子树,而在索引为 [2,5)区间是节点的右子树。

        子问题:那么现在得到了左子树的前序序列 pre = { 9 } ,左子树的中序序列 in = { 9 },接下来的流程跟以上的流程是一样的,先找到该子树的根节点值 9 ,然后创建一个值为 9 的根节点。接着,遍历中序序列来找到根节点的值,该根节点的左部分就是左子树,该节点的右部分就是右子树。那么这里的左右子树都为空,因此节点为 9 的根节点没有左右子树了。

        往上回溯:来到根节点值为 3 的节点。现在得到了右子树的前序序列 pre = {20,15,7} ,右子树的中序序列 in = {15,20,7} ,接下来的过程是一摸一样的,先找到该子树的根节点值为 20 ,创建值为 20 的根节点。然后在中序序列中进行遍历找到根节点的左右子树 :左子树序列为 {15},右子树序列为 {7},接着在前序序列中找左右子树:左子树序列为 {15},右子树序列为 {7} 。又得到了左右前中序列,按同样的道理继续下去即可,通过上面的结论,当左子树前序 {15} 与左子树中序 {15} 一样时,那么在当前的节点值为 15 的根节点没有左右子树了。同理,当右子树前序 {7} 与右子树中序 {7} 一样时,那么在当前的节点值为 7 的根节点没有左右子树了。

        最后回溯,根节点值为 20 的左子树的根节点为 15,右子树的根节点为 7 ,链接起来,一直回溯到结束返回的最后的节点就是该树的根节点(值为 1 的根节点)。

        需要注意的是:注意左闭右开。因为是同一颗树,在前序中的左右子树的长度跟中序中的左右子树的长度是一样的。

        1.2 代码实现从前序与中序遍历序列来构造二叉树

    //根据前序与中序来构造二叉树
    public TreeNode prevAndInOrderConstructTree(int[] prevOrder, int[] inOrder) {
        if (prevOrder.length == 0) {
            return null;
        }
        int rootValue = prevOrder[0];
        TreeNode root = new TreeNode(rootValue);
        for (int i = 0; i < inOrder.length; i++) {
            if (inOrder[i] == rootValue) {
                int[] inLeft = Arrays.copyOfRange(inOrder,0,i);
                int[] inRight = Arrays.copyOfRange(inOrder,i+1,inOrder.length);

                int[] prevLeft = Arrays.copyOfRange(prevOrder,1,i + 1);
                int[] prevRight = Arrays.copyOfRange(prevOrder,i+1,inOrder.length);

                root.left = prevAndInOrderConstructTree(prevLeft,inLeft);
                root.right = prevAndInOrderConstructTree(prevRight,inRight);
            }
        }
        return root;
    }

        只要某一个序列无论是前序或者是中序序列的长度为 0 ,都代表创建二叉树过程结束了。

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

题目:

        给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。

示例 1:

Java LeetCode篇-深入了解二叉树的经典解法(多种方式实现:构造二叉树),Java LeetCode篇,leetcode,职场和发展,java,数据结构

输入:inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出:[3,9,20,null,null,15,7]

OJ链接:

106. 从中序与后序遍历序列构造二叉树

        2.1 实现从中序与后序遍历序列后遭二叉树思路

        具体思路为:中序的序列先访问左子树,再访问根节点,最后到右子树。后序的序列先访问左子树,再访问右子树,最后才到根节点。因此,可以从后序序列中的最后一个元素得到根节点的值,然后利用该值来创建根节点。接着,在中序序列中遍历查找根节点的值,在中序序列中根节点值左边的序列为左子树序列,在中序序列中根节点的右边为右子树的序列。再接着再后序中获取左子树的序列:从索引为 0 开始长度是中序序列得到的左子树的长度;从后序序列中获取右子树序列:除了左子树的序列和根节点值元素,其余就是右子树的序列了。接下来就是子问题了,递归下去,返回当前的根节点。

Java LeetCode篇-深入了解二叉树的经典解法(多种方式实现:构造二叉树),Java LeetCode篇,leetcode,职场和发展,java,数据结构

        具体例子:中序序列 in = {9,3,15,20,7},后序序列 post = {9,15,7,20,3},通过后序得到该树的根节点的值 3,由这个值来创建值为 3 的根节点。接着通过遍历中序序列,找到值为 3 来定位左右子树,左子树的序列为:{9} ,右子树的序列为:{15,20,7} 。再从中序序列中定位左右子树,左子树为:{9},右子树为:{15,7,20} 。现在得到了左右中后序列,中序左子树:{9} ,后序左子树:{9},通过后序得到根节点,再从中序定位该子树的根节点,这里根节点值为 9 的根节点的左右子树均为 null 。接着回溯,返回的该子树的根节点。

        再到右子树中序 {15,20,7} ,右子树后序 {15,7,20},通过后序序列的最后一个值来创建该子树的根节点,在中序中遍历找到该根节点的值,定位该节点的左右子树。中序的左子树序列 {15},右子树序列 {7};后序的左子树序列 {15},后序的右子树序列 {7} 。

        再接着递归,得到左子树中序 {15} ,左子树后序 {15}。通过后序的最后一个元素就是根节点的值来创建该子树的根节点,然后在中序中定位该根节点的左右子树,这里的左右子树都为 null ,返回根节点即可。得到右子树中序 {7},右子树后序 {7},通过后序的最后一个元素为根节点的值来创建该子树的根节点,然后在中序中定位该根节点的左右子树,恰好,这里的左右子树都为 null ,返回根节点即可。

        最后回溯过程,根节点值为 1 的节点的左子树的根节点为 9 的节点,右子树的根节点为 20 的节点。

        2.2 代码实现从中序与后序遍历序列来构造二叉树

    //根据中序与后序来构造二叉树
    public TreeNode inAndPostConstructTree(int[] inOrder, int[] postOrder) {

        if (inOrder.length == 0) {
            return null;
        }
        int rootValue = postOrder[postOrder.length-1];
        TreeNode root = new TreeNode(rootValue);
        for (int j = 0; j < inOrder.length; j++) {
            if (rootValue == inOrder[j]) {
                int[] inLeft = Arrays.copyOfRange(inOrder,0,j);
                int[] inRight = Arrays.copyOfRange(inOrder,j+1,inOrder.length);

                int[] postLeft = Arrays.copyOfRange(postOrder,0,j);
                int[] postRight = Arrays.copyOfRange(postOrder,j,postOrder.length-1);

                root.left = inAndPostConstructTree(inLeft,postLeft);
                root.right = inAndPostConstructTree(inRight,postRight);
            }
        }
        return root;

    }

        需要注意的定位左右子树的序列长度,中序与后序的左右子树都是一一对应的。也因此,当无论任意一个序列结束,都代表着构造二叉树过程结束。

        3.0 根据后缀表达式创建二叉树

        后缀表达式也叫逆波兰表达式,是一种不需要括号的表达式表示方法。在后缀表达式中,运算符总是在操作数的后面,因此可以通过从左到右扫描表达式来创建二叉树。

        3.1 实现后缀表达式创建二叉树思路

        具体思路为:若遇到数字将其压入栈中;若遇到操作符时,将栈中的右左元素弹出栈,操作符节点进行链接弹出来的左右子树,需要注意的是,第一个弹出来的是右操作数,第二个才是左操作数。链接完之后,将其压入栈中即可。循环结束条件为:将后缀表达式遍历完就结束。最后返回栈中的栈顶元素,就是该树的根节点。

        3.2 代码实现后缀表达式创建二叉树

    //根据后缀表达式创建二叉树
    public TreeNode suffixCreateTree(String[] s) {

        LinkedList<TreeNode> stack = new LinkedList<>();
        for (int i = 0; i < s.length; i++) {
            String ch = s[i];
            switch (ch) {
                case "+","-","*","/" -> {
                    TreeNode right = stack.pop();
                    TreeNode left = stack.pop();
                    TreeNode t = new TreeNode(ch);
                    t.right = right;
                    t.left = left;
                    stack.push(t);
                }
                default -> {
                    stack.push(new TreeNode(ch));
                }
            }

        }
        return stack.peek();
    }

         4.0 相同的树

题目:

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

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

示例 1:

Java LeetCode篇-深入了解二叉树的经典解法(多种方式实现:构造二叉树),Java LeetCode篇,leetcode,职场和发展,java,数据结构

输入:p = [1,2,3], q = [1,2,3]
输出:true

OJ链接:

100. 相同的树

        4.1 实现判断两颗树是否相同思路

        具体思路为:使用递归实现,第一种情况:若一个子树为 null ,另一个子树不为 null ,返回 false ;第二种情况:若两个子树都为 null ,则返回 true 。第三种情况:若两个子树的根节点的值不相同时,返回 false 。子过程,判断完左子树,还需判断右子树。

        4.2 代码实现相同树

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);
    }
}

        5.0 另一颗树的子树

题目:

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

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

示例 1:

Java LeetCode篇-深入了解二叉树的经典解法(多种方式实现:构造二叉树),Java LeetCode篇,leetcode,职场和发展,java,数据结构

输入:root = [3,4,5,1,2], subRoot = [4,1,2]
输出:true

OJ链接:

572. 另一棵树的子树

         5.1 实现判断是否为另一颗树的子树

        具体思路为:最根本的问题就是判断是否为相同的树,判断该树的子树与另一颗子树是否相同,不断递归下去,只要相同就返回 true 。直到最后递归结束都没有匹配,则返回 false 。

        5.2 代码实现判断是否为另一颗树的子树

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root == null) {
            return false;
        }
        if(isSameTree(root,subRoot)) {
            return true;
        }
        if(isSubtree(root.left,subRoot)) {
            return true;
        }
        if(isSubtree(root.right,subRoot)) {
            return true;
        }
        return false;

    }
        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);
    }
}

Java LeetCode篇-深入了解二叉树的经典解法(多种方式实现:构造二叉树),Java LeetCode篇,leetcode,职场和发展,java,数据结构文章来源地址https://www.toymoban.com/news/detail-753892.html

到了这里,关于Java LeetCode篇-深入了解二叉树的经典解法(多种方式实现:构造二叉树)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • Java LeetCode篇-二叉搜索树经典解法(实现:二叉搜索树的最近公共祖先、根据前序遍历建树等)

    🔥博客主页: 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍    文章目录         1.0 判断合法         1.1 使用遍历方式实现验证二叉搜索树         1.2 使用递归方式实现验证二叉搜索树         2.0 求范围和         2.1 使用非递归实现二叉搜索树的范围和

    2024年02月03日
    浏览(45)
  • Java LeetCode篇-深入了解关于栈的经典解法(栈实现:中缀表达式转后缀)

    🔥博客主页: 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍     文章目录         1.0 中缀表达式转后缀说明         1.1 实现中缀表达式转后缀思路         2.0 逆波兰表达式求值         2.1 实现逆波兰表达式求值思路         3.0 有效的括号         3.1 实现有

    2024年02月04日
    浏览(58)
  • LeetCode: 二叉树的直径(java)

    543题:二叉树的直径 给你一棵二叉树的根节点,返回该树的 直径 。 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。 两节点之间路径的 长度 由它们之间边数表示。 输入:root = [1,2,3,4,5] 输出:3 解释:3 ,取路径

    2024年02月06日
    浏览(39)
  • leetcode199. 二叉树的右视图(java)

    来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/binary-tree-right-side-view 给定一个二叉树的 根节点 root,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。 示例1: 输入: [1,2,3,null,5,null,4] 输出: [1,3,4] 示例 2: 输入: [1,null,3] 输出: [1,3] 示例 3: 输入

    2024年02月09日
    浏览(31)
  • leetcode111. 二叉树的最小深度(java)

    来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/minimum-depth-of-binary-tree 给定一个二叉树,找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明:叶子节点是指没有子节点的节点。 示例1: 输入:root = [3,9,20,null,null,15,7] 输出:2 示例2: 输入:

    2024年02月09日
    浏览(35)
  • 【Py/Java/C++三种语言详解】LeetCode每日一题240216【二叉树BFS】LeetCode103、二叉树的层序遍历II

    有LeetCode交流群/华为OD考试扣扣交流群可加: 948025485 可上全网独家的 欧弟OJ系统 练习华子OD、大厂真题 绿色聊天软件戳 od1336 了解算法冲刺训练 LeetCode103、二叉树的锯齿形层序遍历 给你二叉树的根节点 root ,返回其节点值的 锯齿形层序遍历 。(即先从左往右,再从右往左进

    2024年02月20日
    浏览(38)
  • ​LeetCode解法汇总823. 带因子的二叉树

    https://github.com/September26/java-algorithms 给出一个含有不重复整数元素的数组  arr  ,每个整数  arr[i]  均大于 1。 用这些整数来构建二叉树,每个整数可以使用任意次数。其中:每个非叶结点的值应等于它的两个子结点的值的乘积。 满足条件的二叉树一共有多少个?答案可能很

    2024年02月10日
    浏览(33)
  • 【深度优先】【广度优先】Leetcode 104 二叉树的最大深度 Leetcode 111 二叉树的最小深度 Leetcode 110 平衡二叉树

    二叉树节点的深度: 指从根节点到该节点的最长简单路径边的条数或者节点数 (取决于深度从0开始还是从1开始) 二叉树节点的高度: 指从该节点到叶子节点的最长简单路径边的条数后者节点数 (取决于高度从0开始还是从1开始) 【前序求的是深度,后序求的是高度】 -

    2024年02月19日
    浏览(52)
  • ​LeetCode解法汇总2385. 感染二叉树需要的总时间

    https://github.com/September26/java-algorithms 给你一棵二叉树的根节点  root  ,二叉树中节点的值  互不相同  。另给你一个整数  start  。在第  0  分钟, 感染  将会从值为  start  的节点开始爆发。 每分钟,如果节点满足以下全部条件,就会被感染: 节点此前还没有感染。 节点

    2024年04月24日
    浏览(41)
  • 【Leetcode60天带刷】day14二叉树——144.二叉树的前序遍历,145.二叉树的后序遍历,94.二叉树的中序遍历

    144. 二叉树的前序遍历 给你二叉树的根节点  root  ,返回它节点值的  前序   遍历。 示例 1: 示例 2: 示例 3: 示例 4: 示例 5: 提示: 树中节点数目在范围  [0, 100]  内 -100 = Node.val = 100 145. 二叉树的后序遍历 给你一棵二叉树的根节点  root  ,返回其节点值的  后序遍历

    2024年02月10日
    浏览(50)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包