Loading [MathJax]/jax/input/TeX/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >算法练习(12)-二叉树的递归套路

算法练习(12)-二叉树的递归套路

作者头像
菩提树下的杨过
发布于 2021-11-02 08:19:16
发布于 2021-11-02 08:19:16
44000
代码可运行
举报
运行总次数:0
代码可运行

如果二叉树的问题,可以分解为 先处理左树, 再处理右侧, 这种就可以用"左程云"推荐的所谓"递归套路"解法, 其代码模板大致象下面这样:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class ReturnType{
    //定义要返回的信息
    public ... ;

    //构造函数
    public ReturnType(...){

    }
}

ReturnType process(TreeNode n){
    //退出递归的base条件
    if (n==null){
        ...
    }

    //向左树要信息
    ReturnType leftData = process(n.left);
    //向右树要信息
    ReturnType rightData = process(n.right);

    //...组装最终结果
    return new ReturnType(...);
}

来看几个示例: (注: 以下题目从效率上讲, 可能有更好的解法, 这里只是为了演示如何使用左神的这个递归思路)

示例1: 求二叉树的高度和节点总数?

思路: 整颗树的节点总数 ,等于左子树的节点数+右子树的节点数, 高度=max(左子树的高度, 右子树的高度), 所以这个问题可以分解为 不停向 左 、右子树 要 高度(height)及节点数(size)

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
/**
 * 先定义左、右子树需要返回的信息体
 */
static class ReturnType {
    public int height;
    public int size;

    public ReturnType(int h, int size) {
        this.height = h;
        this.size = size;
    }
}

/**
 * 再递归调用
 * @param x
 * @return
 */
static ReturnType process(TreeNode x) {
    //退出递归的边界判断
    if (x == null) {
        return new ReturnType(0, 0);
    }
    //向左树要信息
    ReturnType leftData = process(x.left);
    //向右树要信息
    ReturnType rightData = process(x.right);
    
    //组装左树+右树的信息
    return new ReturnType(Math.max(leftData.height, rightData.height) + 1, leftData.size + rightData.size + 1);
}

示例2:如何判断一颗树是满二叉树?

思路:满二叉树的特性, 最后一层叶子节点都是左右双全的, 而且左\右子树的高度相等, 如果这2个条件满足, 必然节点总数=2^k -1 , 即2的k次方,再减1( 注:k为树的高度)

示例1中, 已经求出了节点数, 以及高度k,只要校验一下size是否等于2^height -1

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
 /**
     * 先定义左、右子树需要返回的信息体
     */
    static class ReturnType {
        public int height;
        public int size;
        //这个变量,不用左右子树返回,只是放在这里方便最终使用而已
        public boolean isFBT = false;

        public ReturnType(int h, int size) {
            this.height = h;
            this.size = size;
        }
    }

    /**
     * 判断是否满二叉树(Full Binary Tree)
     *
     * @param x
     * @return
     */
    static ReturnType process(TreeNode x) {
        //退出递归的边界判断
        if (x == null) {
            return new ReturnType(0, 0);
        }
        //向左树要信息
        ReturnType leftData = process(x.left);
        //向右树要信息
        ReturnType rightData = process(x.right);

        int height = Math.max(leftData.height, rightData.height) + 1;
        int size = leftData.size + rightData.size + 1;

        //组装左树+右树的信息
        ReturnType returnType = new ReturnType(height, size);
        //检查总节点数符合满2叉树特点
        returnType.isFBT = ((1 << height) - 1) == size;
        return returnType;
    }

示例3:如何判断一颗树是平衡二叉树?

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
   /**
     * 先定义左、右子树需要返回的信息体
     */
    static class ReturnType {
        public int height;
        //这个变量,不用左右子树返回,只是放在这里方便最终使用而已
        public boolean isAVL = false;

        public ReturnType(int h) {
            this.height = h;
        }
    }

    /**
     * 判断是否满平衡二叉树
     *
     * @param x
     * @return
     */
    static ReturnType process(TreeNode x) {
        //退出递归的边界判断
        if (x == null) {
            return new ReturnType(0);
        }
        //向左树要信息
        ReturnType leftData = process(x.left);
        //向右树要信息
        ReturnType rightData = process(x.right);

        int height = Math.max(leftData.height, rightData.height) + 1;


        //组装左树+右树的信息
        ReturnType returnType = new ReturnType(height);
        returnType.isAVL = Math.abs(leftData.height - rightData.height) <= 1;
        return returnType;
    }

示例4:如何判断一颗树是搜索二叉树?

思路:搜索二叉树的特征, 左边的节点, 肯定比自己小, 右边的节点比自己大. (假设树中没有重复节点) , 违反这个规则就不是搜索二叉树了, 所以可分解为不停向左\右子树询问 "你是不是搜索二叉树? 你的最大节点和最小节点值是多少?"

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
static class ReturnType {
    public boolean isBst;
    public int min = Integer.MIN_VALUE;
    public int max = Integer.MAX_VALUE;

    public ReturnType(boolean bst, int min, int max) {
        this.isBst = bst;
        this.min = min;
        this.max = max;
    }
}

static ReturnType process(TreeNode n) {
    if (n == null) {
        return null;
    }
    ReturnType leftData = process(n.left);
    ReturnType rightData = process(n.right);
    int min = n.val;
    int max = n.val;
    if (leftData != null) {
        min = Math.min(min, leftData.min);
        max = Math.max(max, leftData.max);
    }
    if (rightData != null) {
        min = Math.min(min, rightData.min);
        max = Math.max(max, rightData.max);
    }
    boolean isBst = true;
    //左树不是搜索树, 或左树的最大节点比自己还大, 整体必然不是搜索二叉树
    if (leftData != null && (!leftData.isBst || leftData.max >= n.val)) {
        isBst = false;
    }
    //右树不是搜索树, 或右树的最小节点比自己还小, 整体必然不是搜索二叉树
    if (rightData != null && (!rightData.isBst || rightData.min <= n.val)) {
        isBst = false;
    }
    return new ReturnType(isBst, min, max);
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2021-10-31 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
二叉树遍历的应用:判断二叉树的类别
昨天的文章讲述了二叉树的先序、中序和后序的遍历方法(递归和非递归),但是这种遍历方法有什么意义么?今天来讲讲这些算法可以用来做什么,只要稍加更改,我们就可以得到另外一个功能,只需要仅仅几行代码的修改! 还记得上篇文章二叉树的分类么?今天我们要来说三种树的分类:完全二叉树、平衡二叉树和搜索二叉树!
算法工程师之路
2019/08/05
5450
树形DP
 假设现在有一棵树,我只要求出每个结点作为头节点对应子树的最大值和最小值,那么最终答案一定在其中,因此每个结点都有两个信息,最大值和最小值,我把这个信息封装为一个结构体,带入递归中,就能求出最终答案,最大值就等于当前结点左子树的最大值和右子树的最大值和当前结点的值三者中最大的那一个,最小值也是三者中最小的那一个。
mathor
2018/08/16
1.6K0
树形DP
LeetCode110.平衡二叉树
 平衡二叉树的定义是一个二叉树每个结点的左右两个子树的高度差绝对值不超过1(可以是1),用一个结构体来保存某个结点的信息(包括是否是平衡树,高度多少),算法流程如下:
mathor
2018/08/17
4940
LeetCode110.平衡二叉树
【算法】论平衡二叉树(AVL)的正确种植方法
参考资料 《算法(java)》                           — — Robert Sedgewick, Kevin Wayne 《数据结构》                                  — — 严蔚敏 2017年度原创IT博客评选:http://www.itbang.me/goVote/203 引子 近日, 为了响应市政府“全市绿化”的号召, 身为共青团员的我决定在家里的后院挖坑种二叉树,以支援政府实现节能减排的伟大目标,并进一步为实现共同富裕和民族复兴打下坚实
啦啦啦321
2018/03/30
1.1K0
【算法】论平衡二叉树(AVL)的正确种植方法
什么是平衡二叉树
上篇文章里面,我们已经学习了二叉搜索树的相关内容,二叉搜索树有一个缺点,在插入数据是有序的序列(包括升序和降序),会导致二叉树退化成链表,从而导致在查找,删除,添加时的性能均从O(logN)降低为O(N),这是不能接受的。如下图:
我是攻城师
2019/04/28
7.4K0
什么是平衡二叉树
【算法】搜索二叉树,完全二叉树,平衡二叉树的判断
它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
MapleYe
2020/03/28
1.1K0
AVL树(平衡二叉树)
为什么叫AVL树?   因为AVL树是由 G.M.Adelson-Velsky 和 E.M.Landis 这两位俄罗斯科学家在1962年的论文中首次提出,是最早的自平衡二分搜索树结构。   由于AVL树是自平衡二分搜索树,所以本质上还是二分搜素树,也就是二分搜索树的性质AVL树都满足,由于二分搜索树在添加有序元素时,会退化成链表,造成时间复杂度为O(n),但AVL树是不会出现这种情况的,因为AVL树通过自平衡来解决了退化成链表的问题,关于二分搜索树,你可以看我之前二分搜索树(Binary Search Tree)这篇文章。 平衡二叉树:对于任意一个节点,左子树和右子树的高度差都不能超过1。
程序员波特
2024/01/19
1920
AVL树(平衡二叉树)
自已动手作图搞清楚AVL树
二叉树是一种常用的数据结构,更是实现众多算法的一把利器。 二分搜索树(Binary Search Tree)做为一种能实现快速定位查找的二叉树也得到了广泛应用
智慧zhuhuix
2020/08/14
6470
自已动手作图搞清楚AVL树
【算法】二叉查找树(BST)实现字典API
该文介绍了在技术社区中如何从技术角度、业务角度、架构角度、工程角度、团队协作角度、社区运营角度、软件工程角度、编程语言角度去分析思考问题,通过实例介绍了这些方法的应用,并总结了一些思考框架。
啦啦啦321
2018/01/03
1.7K0
【算法】二叉查找树(BST)实现字典API
二叉树刷题总结:二叉树的属性
这就需要去判断根节点下左子树与右子树里侧和外侧是否相等。比较的方法是拿左子树的 “左-右-中” 节点和右子树的“右-左-中”为顺序的节点做比较。
HelloWorld杰少
2022/08/04
3760
二叉树刷题总结:二叉树的属性
【算法总结】五道常见的算法-二叉树
前段时间,写了面试必备的一系列文章,反应还不错。有一些读者反馈说,能不能整理一些面试常见的算法。前段时间,我恰好总结了 LeetCode 常见的面试算法题目。
程序员徐公
2022/01/20
1.1K0
【算法总结】五道常见的算法-二叉树
数据结构之AVL树
我们先来回忆一下二分搜索树所存在的一个问题:当我们按顺序往二分搜索树添加元素时,那么二分搜索树可能就会退化成链表。例如,现在有这样一颗二分搜索树:
端碗吹水
2021/02/02
5250
【数据结构】二叉树全攻略,从实现到应用详解
树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。
2的n次方
2024/10/15
1980
【数据结构】二叉树全攻略,从实现到应用详解
LeetCode 二叉树系统题解
TIPS:前中后序遍历区别在于三字中的中间那个字,前、中、后序分别对应左、根、右。
Yano_nankai
2019/11/10
9940
LeetCode 二叉树系统题解
二叉树的最大深度
使用前序(中左右),也可以使用后序遍历(左右中),使用前序求的就是深度,使用后序求的是高度。
用户11097514
2024/05/30
860
美团面试官:你对二叉树后续遍历一无所知
其实二叉树的题目真的不难,无非就是前中后序遍历框架来回倒嘛,但是对于有的题目,不同的遍历顺序时间复杂度不同。
labuladong
2021/09/23
5560
二叉树的操作及常见面试题
本文将附上博主自己手动实现的二叉树常见的各种操作以及归纳总结一下常见的基础面试题。
VIBE
2022/12/02
3890
二叉树——104. 二叉树的最大深度
方法一:深度优先搜索 如果我们知道了左子树和右子树的最大深度Ⅰ和r,那么该二叉树的最大深度即为 max(l, r)+1 而左子树和右子树的最大深度又可以以同样的方式进行计算。因此我们可以用「深度优先搜索」的方法来计算二叉树的最大深度。具体而言,在计算当前二叉树的最大深度时,可以先递归计算出其左子树和右子树的最大深度,然后在O(1)时间内计算出当前二叉树的最大深度。递归在访问到空节点时退出。 复杂度分析 时间复杂度:O(n),其中n为二叉树节点的个数。每个节点在递归中只被遍历一次。 空间复杂度:O(height),其中height表示二叉树的高度。递归函数需要栈空间,而栈空间取决于递归的深度,因此空间复杂度等价于二叉树的高度。 方法二:广度优先搜索 我们也可以用「广度优先搜索」的方法来解决这道题目,但我们需要对其进行—些修改,此时我们广度优先搜索的队列里存放的是「当前层的所有节点」。每次拓展下一层的时候,不同于广度优先搜索的每次只从队列里拿出一个节点,我们需要将队列里的所有节点都拿出来进行拓展,这样能保证每次拓展完的时候队列里存放的是当前层的所有节点,即我们是一层一层地进行拓展,最后我们用一个变量ans来维护拓展的次数,该二叉树的最大深度即为ans。 复杂度分析 ·时间复杂度:O(n),其中n为二叉树的节点个数。与方法一同样的分析,每个节点只会被访问一次。 ·空间复杂度:此方法空间的消耗取决于队列存储的元素数量,其在最坏情况下会达到O(n)。
向着百万年薪努力的小赵
2022/12/02
2940
二叉树——104. 二叉树的最大深度
计算二叉树的最大高度
参考链接:Iterative Method to find Height of Binary Tree
九州暮云
2019/08/21
5K0
为实习准备的数据结构(4)-- 二叉树
==特别标注:如果二叉树中有相同值元素的存在,那么有极大概率还原失败,下面中、后序遍历也是==
看、未来
2021/03/17
4170
相关推荐
二叉树遍历的应用:判断二叉树的类别
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验