二叉树入门算法题详解

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

二叉树入门题目详解

首先知道二叉树是什么:

代码随想录 (programmercarl.com)
了解后知道其实二叉树就是特殊的链表,只是每个根节点节点都与两个子节点相连而其实图也是特殊的链表,是很多节点互相连接;这样说只是便于理解和定义,严格来说他们都是不同的数据结构了,在使用中还是要牢记各种数据结构的性质的。

二叉树的存储方式

链式的:

java

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

对于二叉树一定会第一时间想到递归,他们俩是相辅相成,互相存在的

就比如说简单的二叉树遍历就用到了递归

前序遍历:中左右

中序遍历:左中右

后序遍历:左右中

二叉树的递归遍历

// 前序遍历·递归·LC144_二叉树的前序遍历
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        preorder(root, result);
        return result;
    }

    public void preorder(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        result.add(root.val);
        preorder(root.left, result);
        preorder(root.right, result);
    }
}
// 中序遍历·递归·LC94_二叉树的中序遍历
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inorder(root, res);
        return res;
    }

    void inorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        inorder(root.left, list);
        list.add(root.val);             // 注意这一句
        inorder(root.right, list);
    }
}
// 后序遍历·递归·LC145_二叉树的后序遍历
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        postorder(root, res);
        return res;
    }

    void postorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        postorder(root.left, list);
        postorder(root.right, list);
        list.add(root.val);             // 注意这一句
    }
}

二叉树的层序遍历

其实可以说前边的递归遍历是深度遍历,那么层序就是字面意思,一层一层遍历,如何能一层一层遍历呢,我们想到了队列,以及父节点和子节点的关系,即先有父节点,后有子节点,子节点连着父节点,所以

当使用队列时,可以先把父节点放进去,有父节点就可以找出对应的子节点,把父节点的子节点也放进去,再把父节点输出出去,队列中剩下的就是子节点,再找到对应的子子节点,这时就可以把子节点输出出去,聪明点的已经发现了,我们现在输出的顺序就像是层序遍历,是的,层序就是这么一个过程。

这中间需要有一个用来描述此时这层节点个数的变量来中转,因为每层的节点个数都不同,

分为递归和借助队列两种方式

借助队列:更容易理解上边的过程:

class Solution {
    public List<List<Integer>> resList = new ArrayList<List<Integer>>();

    public List<List<Integer>> levelOrder(TreeNode root) {
  
        checkFun02(root);

        return resList;
    }  
//BFS--迭代方式--借助队列
    public void checkFun02(TreeNode node) {
        if (node == null) return;
        Queue<TreeNode> que = new LinkedList<TreeNode>();
        que.offer(node);

        while (!que.isEmpty()) {
            List<Integer> itemList = new ArrayList<Integer>();
            int len = que.size();

            while (len > 0) {
                TreeNode tmpNode = que.poll();
                itemList.add(tmpNode.val);

                if (tmpNode.left != null)  que.offer(tmpNode.left);
                if (tmpNode.right != null) que.offer(tmpNode.right);
                len--;
            }

            resList.add(itemList);
        }

    }

翻转二叉树:

其实就是使用递归先把二叉树的每个左右节点都交换一遍,再遍历一遍,得到的新的就是翻转的

java

class Solution {
   /**
     * 前后序遍历都可以
     * 中序不行,因为先左孩子交换孩子,再根交换孩子(做完后,右孩子已经变成了原来的左孩子),再右孩子交换孩子(此时其实是对原来的左孩子做交换)
     */
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        //以后序遍历为例
        invertTree(root.left);   //左
        invertTree(root.right);  //右
        swapChildren(root);      //中
        //虽然先遍历左右子树,但第三步到根节点时会改变其左右子树,所以仍然正确,先写中,左右,其实效果是一样的;
        return root;             
    }

    private void swapChildren(TreeNode root) {
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
    }
}

对称二叉树

二叉树入门算法题详解,算法,java

如图

我们可以想象一下后序遍历时,

左侧:5 6 3 4 2 右侧: 4 6 5 3 2 中:1

再结合图片看待,对于左子树其实是按照左右中遍历,

右子树其实可以看做左子树按照右左中的顺序遍历;

所以对于对称二叉树,可以使用后序遍历左子树,并将右子树再按照右左中的顺序遍历,若两者结果一样,那么可以判断是对称二叉树;(找规律,细微之处见斟酌)(想法很不错,现实很骨感,只有后序是不能唯一确认二叉树的);

而对于代码怎么写,是比上边的推理要麻烦一些的,因为,即使两个子树不同,只有先序遍历一种写法,是没办法唯一确认一颗二叉树的!!!

所以我们需要另想办法:再观察,其实递归遍历左子树和右子树,是将每次递归中的左右子树的左右子树对称点的值是否相同,若相同其结果就一样,所以代码条件就变成了,递归遍历二叉树并且每次递归都是带上左右子树,每次都遍历到对称的两边,左节点的子节点应始终和右节点的子节点对称,即:若左为空,右也为空,不为空时,左值应=右值;(过瘾)

java:
(每次先看了c++的代码,再看java写这种链表和二叉树的题目代码是真的复杂。。。)

class Solution {
    public boolean isSymmetric(TreeNode root) {

        return compare(root.left, root.right);
    }

    private boolean compare(TreeNode left, TreeNode right) {

        if (left == null && right != null) {
            return false;
        }
        if (left != null && right == null) {
            return false;
        }

        if (left == null && right == null) {
            return true;
        }
        if (left.val != right.val) {
            return false;
        }
        // 比较外侧
        boolean compareOutside = compare(left.left, right.right);
        // 比较内侧
        boolean compareInside = compare(left.right, right.left);
        return compareOutside && compareInside;
    }
}

参考c++的:

class Solution {
public:
    bool compare(TreeNode* left, TreeNode* right) {
        // 首先排除空节点的情况
        if (left == NULL && right != NULL) return false;
        else if (left != NULL && right == NULL) return false;
        else if (left == NULL && right == NULL) return true;
        // 排除了空节点,再排除数值不相同的情况
        else if (left->val != right->val) return false;

        // 此时就是:左右节点都不为空,且数值相同的情况
        // 此时才做递归,做下一层的判断
        bool outside = compare(left->left, right->right);   // 左子树:左、 右子树:右
        bool inside = compare(left->right, right->left);    // 左子树:右、 右子树:左
        bool isSame = outside && inside;                    // 左子树:中、 右子树:中 (逻辑处理)
        return isSame;
    }
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        return compare(root->left, root->right);
    }
};

二叉树的最大深度

二叉树入门算法题详解,算法,java

怎么求呢?直接使用递归求出根节点对应的最大高度就是该二叉树的最大深度啦

java

class solution {
    /**
     * 递归法
     */
    public int maxDepth(TreeNode root) {
        //空节点高度为0,置为return 0,则叶子结点高度一定都为1,越往上的父节点每次都加1;
        if (root == null) {
            return 0;
        }
        int leftDepth = maxDepth(root.left);    //左
        int rightDepth = maxDepth(root.right);  //右
        return Math.max(leftDepth, rightDepth) + 1; //中:高度为左右中的最大值+1;
    }
}

二叉树的最小深度

方法和求最大深度有点像,又不太一样;

当只把最大改最小时会犯以下的错误。需要对节点的字节点都进行判断,当两子节点都为空时才是叶子节点;

易错点:

class Solution {
    /**
     * 递归法
     */
    public int minDepth(TreeNode root) {
        //空节点高度为0,置为return 0,则叶子结点高度一定都为1,越往上的父节点每次都加1;
        if (root == null) {//意思是左右节点都为空
            return 0;
        }
        int leftDepth = minDepth(root.left);    //左
        int rightDepth = minDepth(root.right);  //右
        if (root.left==null){// 只有左节点为空,返回的最小值只能为右节点+1
            return rightDepth+1;
        }
        if(root.right ==null){//只有右节点为空,返回的最小值只能为左节点+1
            return leftDepth+1;
        }
        return Math.min(leftDepth, rightDepth) + 1; //中:高度为左右中的最小值+1;
    //
    }
}

完全二叉树的节点个数

二叉树入门算法题详解,算法,java

二叉树入门算法题详解,算法,java

仔细思考,这道题其实和求二叉树的最大深度很类似,只不过那道题是取左右深度的最大值,这个就可以写成求左右深度+1(就是这个子树的节点个数了)文章来源地址https://www.toymoban.com/news/detail-835373.html

class solution {
    /**
     * 递归法
     */
    public int Number(TreeNode root) {
        //空节点高度为0,置为return 0,则叶子结点高度一定都为1,越往上的父节点每次都加1;
        if (root == null) {
            return 0;
        }
        int leftNumber = Number(root.left);    //左
        int rightNumber = Number(root.right);  //右
        return leftNumber+rightNumber + 1; //中:高度为左右中的最大值+1;
    }
}

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

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

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

相关文章

  • 二叉树遍历之后序遍历(非递归、递归)入门详解

    二叉树的遍历常见的方法有先序遍历、中序遍历、后序遍历和层次遍历等,本文给出了C语言版本的后序遍历二叉树的非递归算法和递归算法。 后序遍历不如先序遍历简单,是相对最复杂的一种遍历方法。访问结点的次序是:“左—右—根”,也就是首先访问左子树,之后访

    2024年02月04日
    浏览(46)
  • 【数据结构】二叉树的遍历递归算法详解

    我们来写一个函数 BuyNode(x)函数 用于创建二叉树结点。 用动态开辟函数 malloc 函数进行动态开辟,并强制转换为 BTNode 型,用变量 node 来去管理开辟的空间。 我们初始化结点,其 val 即为传入的参数x,左右指针 left 和 right 都设为NULL。 我们在主函数中创建上面这样一颗二叉树

    2024年01月20日
    浏览(46)
  • 【数据结构与算法篇】深入浅出——二叉树(详解)

    ​👻内容专栏:《数据结构与算法专栏》 🐨本文概括: 二叉树是一种常见的数据结构,它在计算机科学中广泛应用。本博客将介绍什么是二叉树、二叉树的顺序与链式结构以及它的基本操作,帮助读者理解和运用这一重要概念。 🐼本文作者: 花 蝶 🐸发布时间:2023.6.5

    2024年02月08日
    浏览(50)
  • 数据结构与算法——树与二叉树篇详解

    树形结构是一种非常重要的 非线性结构 ,树形结构中数据元素之间具有 一对多 的逻辑关系。 1.1.1 树的定义 树是由n(n=0)个结点所构成的有限集合 当n=0时,称为空树 当n0时,n个结点满足以下条件 有且仅有一个称为根的结点 其余结点可分为m个互不相交的有限集合,且每一个

    2024年02月06日
    浏览(50)
  • 数据结构与算法----详解二叉树的遍历(迭代、递归)

    ❤️ 作者简介 :大家好我是小鱼干儿♛是一个热爱编程、热爱算法的大三学生,蓝桥杯国赛二等奖获得者 🐟 个人主页 :https://blog.csdn.net/qq_52007481 ⭐ 个人社区 :【小鱼干爱编程】 🔥 算法专栏 :算法竞赛进阶指南 💯 刷题网站 :虽然市面上有很多的刷题网站,但是里面

    2024年01月24日
    浏览(54)
  • 数据结构之树与二叉树——算法与数据结构入门笔记(五)

    本文是算法与数据结构的学习笔记第五篇,将持续更新,欢迎小伙伴们阅读学习。有不懂的或错误的地方,欢迎交流 前面章节介绍的都是线性存储的数据结构,包括数组、链表、栈、队列。本节带大家学习一种非线性存储的数据结构,即树(tree)。 不管是在面试时,还是日

    2024年02月08日
    浏览(50)
  • 【算法与数据结构】深入二叉树实现超详解(全源码优化)

    上节我们学习了二叉树(前中后)序遍历 这节将实现二叉树。 让我们复习一下二叉树,接着就是二叉树的实现了😊,学习起来吧! 满二叉树:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为K,且结点总

    2024年04月11日
    浏览(76)
  • Offer必备算法08_二叉树dfs_六道力扣题详解(由易到难)

    目录 ①力扣2331. 计算布尔二叉树的值 解析代码 ②力扣129. 求根节点到叶节点数字之和 解析代码 ③力扣814. 二叉树剪枝 解析代码 ④​​​力扣98. 验证二叉搜索树 解析代码 ⑤力扣230. 二叉搜索树中第K小的元素 解析代码 ⑥力扣257. 二叉树的所有路径 解析代码 2331. 计算布尔二

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

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

    2024年02月20日
    浏览(40)
  • C++数据结构与算法详解:链表、栈、队列、树、二叉树和图结构的实现与应用

    链表是一种常见的数据结构由一系列节点按顺序连接而成,一般每个节点包含一个数据元素和一个指向下一个节点的引用。 链表有多种类型: 单向链表:每个节点只有一个指向下一个节点的引用 双向链表:每个节点有一个指向前一个节点和一个指向后一个节点的引用 循环链

    2024年02月04日
    浏览(52)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包