专栏：50多种数据结构彻底征服

专栏：50多种经典图论算法全部掌握

台湾知名宝宝摄影机厂商云云科技的52岁董事长曾某，疑因理念不合，持一把30公分长的刀具，残忍杀害了51岁的梁姓技术总监。

原因是曾某要求团队“三个月内上线社交直播功能”。因为“用户增长放缓，投资方要看数据！”而梁某当场反对：“现在的架构根本撑不起直播，强行上线会崩掉！”

这场冲突的本质，是两种逻辑的生死博弈。梁某的“技术优先”逻辑：先修地基，再盖高楼；曾某的“商业优先”逻辑：先抢市场，边跑边补。

三个月后，直播功能如期上线，结果代价惨重，服务器崩溃，用户投诉激增500%；核心工程师离职三分之一；之后曾某将梁某踢出所有管理群组，还当众嘲讽：“某些人只会写代码，根本不懂商业！”。这哪是职场，简直是战场。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第110题平衡二叉树。

问题描述

来源：LeetCode第110题

难度：简单

给定一个二叉树，判断它是否是平衡二叉树。平衡二叉树是指该树所有节点的左右子树的高度相差不超过 1。

示例1：

输入：root = [3,9,20,null,null,15,7] 输出：true

示例2：

输入：root = [1,2,2,3,3,null,null,4,4] 输出：false

  • 树中的节点数在范围 [0, 5000] 内

  • -10^4 <= Node.val <= 10^4

问题分析

这题让判断给定的二叉树是否是平衡二叉树，所谓平衡二叉树就是该二叉树的左右子树高度差的绝对值不能超过 1 ，并且它的任何一颗子树也都是满足这个条件。我们之前讲的就是平衡二叉树。

计算二叉树的高度比较简单，如果是从上往下判断，当根节点平衡之后还需要判断左右两个子树是否平衡，这样树的高度就会出现重复计算，效率比较差。我们可以换一种思路，从下往上判断。

当计算二叉树高度的时候，从下往上如果子树已经出现了不平衡，不要返回二叉树的高度，返回 -1 即可。计算的时候如果子树有返回 -1 的，说明子树已经出现了不平衡，就不需要在计算了，否则就返回二叉树的高度。

JAVA：

public boolean isBalanced(TreeNode root) {     return depth(root) != -1; } // 计算二叉树的高度，如果返回了 -1 ，说明出现了不平衡。 private int depth(TreeNode root) {     if (root == null)         return0;     int left = depth(root.left);// 计算左子树的高度     int right = depth(root.right);// 计算右子树的高度     // 如果左右子树只要有一个返回 -1 ，说明子树出现了不平衡，     // 否则如果左右子树高度差的绝对值大于 1 ，也说明出现了不平衡。     if (left == -1 || right == -1 || Math.abs(left - right) > 1)         return -1;     return1 + Math.max(left, right);// 否则返回二叉树的高度 }

C++：

public:     bool isBalanced(TreeNode *root) {         return depth(root) != -1;     }     // 计算二叉树的高度，如果返回了 -1 ，说明出现了不平衡。     int depth(TreeNode *root) {         if (root == nullptr)             return0;         int left = depth(root->left);// 计算左子树的高度         int right = depth(root->right);// 计算右子树的高度         // 如果左右子树只要有一个返回 -1 ，说明子树出现了不平衡，         // 否则如果左右子树高度差的绝对值大于 1 ，也说明出现了不平衡。         if (left == -1 || right == -1 || abs(left - right) > 1)             return-1;         return1 + max(left, right);// 否则返回二叉树的高度     }

笔者简介

博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。