16_平衡二叉树

简介: 16_平衡二叉树

平衡二叉树

【题外话】

  • 二叉树节点的深度:指从根节点到该节点的最长简单路径边的条数。(从上往下看)
  • 二叉树节点的高度:指从该节点到叶子节点的最长简单路径边的条数。(从下往上看)

小疑惑:为什么104.二叉树的最大深度中求的是二叉树的最大深度,也用的是后序遍历。(本质上求解的就是根节点的高度,而根节点的高度就是这棵树的最大深度,所以才可以使用后序遍历)

【本题思路】

递归

递归三部曲分析:

1、明确递归函数的参数和返回值

参数:当前传入节点。返回值:以当前传入节点为根节点的树的高度。

如何标记左右子树是否差值大于1呢?

如果当前传入节点为根节点的二叉树已经不是二叉平衡树的话,直接返回-1

代码如下:

// -1表示已经不是平衡二叉树了,否则返回值是以该节点为根节点树的高度
int getHeight(TreeNode *node)

2、明确终止条件

递归的过程中仍然是遇到空节点了为终止,返回0,表示当前节点为根节点的树高度为0

代码如下:

int (node == null) {
  return 0;
}

3、确定单层递归的逻辑

如何判断当前传入节点为根节点的二叉树是否是平衡二叉树呢?当然是其左子树高度和其右子树高度的差值。

int leftHeight = getHeight(node.left);  // 左
if (leftHeight == -1)  return -1;
int rightHeight = getHeight(node.right);  //右
if (rightHeight == -1) return -1;
int result;
if (Math.abs(leftHeight - rightHeight) > 1) {  //中
  return -1;
} else {
  result = 1 + max(leftHeight, rightHeight);  //以当前节点为根节点的树的最大高度
}  
return result;

整体递归代码如下:

class Solution {
public boolean isBalanced(TreeNode root) {
        return getHeight(root) == -1 ? false : true;
    }
    /*
    我的想法
    public int getHeight(TreeNode node) {
        if (left == null && right == null) {
            return true;
        }
        int leftDepth = 0;
        int rightDepth = 0;
        while (left.left != null) {
            leftDepth++;
        }
        while (right.right != null) {
            rightDepth++;
        }
        if (Math.abs(leftDepth - rightDepth) > 1) {
            return false;
        } else {
            return true;
        }
        boolean judgeLeft = judge_Balance(left.left, left.right);
        boolean judgeRight = judge_Balance(right.left, right.right);
        return judgeLeft && judgeRight;
    }*/
    public int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = getHeight(root.left);  //左
        if (leftHeight == -1)  return -1;
        int rightHeight = getHeight(root.right);  //右
        if (rightHeight == -1)  return -1;
        int result;
        if (Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        } else {
            result = 1 + Math.max(leftHeight, rightHeight);
        }
        return result;
    }
}

迭代

在104.二叉树的最大深度中我们可以使用层序遍历来求深度,但是就不能直接用层序遍历来求高度了,这就体现出了求高度和求深度的不同。

本题的迭代方式可以先定义一个函数,专门用来求高度。

这个函数用过栈模拟的后序遍历找每一个节点的高度(其实是通过求传入节点为根节点的最大深度来求的高度)

代码如下:

class Solution {
   /**
     * 迭代法,效率较低,计算高度时会重复遍历
     * 时间复杂度:O(n^2)
     */
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;
        while (root!= null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            TreeNode inNode = stack.peek();
            // 右结点为null或已经遍历过
            if (inNode.right == null || inNode.right == pre) {
                // 比较左右子树的高度差,输出
                if (Math.abs(getHeight(inNode.left) - getHeight(inNode.right)) > 1) {
                    return false;
                }
                stack.pop();
                pre = inNode;
                root = null;// 当前结点下,没有要遍历的结点了
            } else {
                root = inNode.right;// 右结点还没遍历,遍历右结点
            }
        }
        return true;
    }
    /**
     * 层序遍历,求结点的高度
     */
    public int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        int depth = 0;
        while (!deque.isEmpty()) {
            int size = deque.size();
            depth++;
            for (int i = 0; i < size; i++) {
                TreeNode poll = deque.poll();
                if (poll.left != null) {
                    deque.offer(poll.left);
                }
                if (poll.right != null) {
                    deque.offer(poll.right);
                }
            }
        }
        return depth;
    }
}
class Solution {
   /**
     * 优化迭代法,针对暴力迭代法的getHeight方法做优化,利用TreeNode.val来保存当前结点的高度,这样就不会有重复遍历
     * 获取高度算法时间复杂度可以降到O(1),总的时间复杂度降为O(n)。
     * 时间复杂度:O(n)
     */
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            TreeNode inNode = stack.peek();
            // 右结点为null或已经遍历过
            if (inNode.right == null || inNode.right == pre) {
                // 输出
                if (Math.abs(getHeight(inNode.left) - getHeight(inNode.right)) > 1) {
                    return false;
                }
                stack.pop();
                pre = inNode;
                root = null;// 当前结点下,没有要遍历的结点了
            } else {
                root = inNode.right;// 右结点还没遍历,遍历右结点
            }
        }
        return true;
    }
    /**
     * 求结点的高度
     */
    public int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = root.left != null ? root.left.val : 0;
        int rightHeight = root.right != null ? root.right.val : 0;
        int height = Math.max(leftHeight, rightHeight) + 1;
        root.val = height;// 用TreeNode.val来保存当前结点的高度
        return height;
    }
}
JAVA 折叠 复制 全屏

总结:

通过本题可以了解求二叉树深度和二叉树高度的差异,求深度适合用前序遍历,而求高度适合用后序遍历。

本题迭代法其实有点复杂,大家可以有一个思路,也不一定说非要写出来。

但是递归方式是一定要掌握的!

相关文章
|
存储 SQL API
milvus insert api流程源码分析
milvus insert api流程源码分析
913 3
|
存储 分布式计算 监控
Hologres产品介绍与技术揭秘
近年来,随着数据实时化的诉求加剧,催生了一系列的实时数仓架构,Lambda架构也应运而生,但是随着场景的复杂度和业务多维需求,Lambda架构的痛点也越来越明显。HSAP的理念则是服务分析一体化,在本文中,来自阿里巴巴的资深技术专家将会深度剖析HSAP技术实现Hologres的设计原理,解读其产品典型场景。
13782 0
Hologres产品介绍与技术揭秘
|
开发工具 git 索引
|
供应链 安全 数据可视化
2025年MES系统厂商排名揭晓:深度解析头部企业如何破解生产数智化难题
树根科技MES系统以“软件+咨询”模式深度融合精益生产与数智化技术,依托根云平台实现设备互联、数据集成与流程固化。其微服务架构支持灵活配置,覆盖计划、生产、质量、仓储等全场景,助力企业提升交付率、缩短周期、实现全流程追溯,为中大型离散制造企业提供高适配、可扩展的智能工厂解决方案。
487 2
|
人工智能 自然语言处理 搜索推荐
贝聿铭的 “数字续作”:蚂蚁百宝箱 × 苏州博物馆,用 AI 重构文化地标
苏州博物馆携手蚂蚁百宝箱推出AI助手“小苏苏”,集成展讯、导览、文创推荐等功能,打造“咨询—导览—消费”闭环,以智能服务提升参观体验,助力文博场馆数字化升级。
955 0
贝聿铭的 “数字续作”:蚂蚁百宝箱 × 苏州博物馆,用 AI 重构文化地标
|
前端开发 Java 微服务
2025 年全网超全 Java 从入门到精通学习路线指南
这是一份全面的Java学习路线图,涵盖从基础到进阶的知识体系。基础阶段包括环境搭建、语法学习与面向对象编程;进阶阶段深入数据结构、多线程、JVM原理及泛型集合;框架阶段掌握Spring、MyBatis等工具;数据库阶段学习SQL、MySQL及Redis;前端技术涉及HTML、CSS与Vue;分布式阶段探讨微服务架构、Docker与Kubernetes;最后通过企业级项目实战提升性能优化与代码重构能力。资源地址:[https://pan.quark.cn/s/14fcf913bae6](https://pan.quark.cn/s/14fcf913bae6)
1808 7
|
数据可视化 算法 数据挖掘
Python量化投资实践:基于蒙特卡洛模拟的投资组合风险建模与分析
蒙特卡洛模拟是一种利用重复随机抽样解决确定性问题的计算方法,广泛应用于金融领域的不确定性建模和风险评估。本文介绍如何使用Python和EODHD API获取历史交易数据,通过模拟生成未来价格路径,分析投资风险与收益,包括VaR和CVaR计算,以辅助投资者制定合理决策。
1516 15
|
存储 传感器 网络协议
异步传输:概念、特点与应用
【8月更文挑战第24天】
1725 0
|
存储 算法 中间件
每日 3000万订单的社区电商要如何分库分表
文章首先介绍了分库分表的基本概念,包括分库、分表及其组合形式,并详细解释了水平切分、垂直切分和混合切分的方式。接着分析了分库分表的原因,如解决性能瓶颈、微服务化需求等。文章还讨论了分库分表的常见问题,如调试难度、分布式事务和跨库查询等,并介绍了分库分表工具的客户端模式和代理模式。最后,通过一个社区电商的真实案例,详细展示了分库分表的具体落地过程,包括评估库表总数、选择分库分表字段等关键步骤。
932 5
|
Ubuntu Linux Docker
【ClickHouse】深入浅出系列之快速部署ClickHouse
【ClickHouse】深入浅出系列之快速部署ClickHouse