專欄：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算法文檔 。