專欄：50多種數(shù)據(jù)結構徹底征服
專欄：50多種經(jīng)典圖論算法全部掌握
臺灣知名寶寶攝影機廠商云云科技的52歲董事長曾某，疑因理念不合，持一把30公分長的刀具，殘忍殺害了51歲的梁姓技術總監(jiān)。
原因是曾某要求團隊“三個月內(nèi)上線社交直播功能”。因為“用戶增長放緩，投資方要看數(shù)據(jù)！”而梁某當場反對：“現(xiàn)在的架構根本撐不起直播，強行上線會崩掉！”
這場沖突的本質，是兩種邏輯的生死博弈。梁某的“技術優(yōu)先”邏輯：先修地基，再蓋高樓；曾某的“商業(yè)優(yōu)先”邏輯：先搶市場，邊跑邊補。
三個月后，直播功能如期上線，結果代價慘重，服務器崩潰，用戶投訴激增500%；核心工程師離職三分之一；之后曾某將梁某踢出所有管理群組，還當眾嘲諷：“某些人只會寫代碼，根本不懂商業(yè)！”。這哪是職場，簡直是戰(zhàn)場。
--------------下面是今天的算法題--------------
來看下今天的算法題，這題是LeetCode的第110題平衡二叉樹。
問題描述
來源：LeetCode第110題
難度：簡單
給定一個二叉樹，判斷它是否是平衡二叉樹。平衡二叉樹是指該樹所有節(jié)點的左右子樹的高度相差不超過 1。
示例1：
輸入：root = [3,9,20,null,null,15,7] 輸出：true
示例2：
輸入：root = [1,2,2,3,3,null,null,4,4] 輸出：false
樹中的節(jié)點數(shù)在范圍 [0, 5000] 內(nèi)
-10^4 <= Node.val <= 10^4
問題分析
這題讓判斷給定的二叉樹是否是平衡二叉樹，所謂平衡二叉樹就是該二叉樹的左右子樹高度差的絕對值不能超過 1 ，并且它的任何一顆子樹也都是滿足這個條件。我們之前講的就是平衡二叉樹。
計算二叉樹的高度比較簡單，如果是從上往下判斷，當根節(jié)點平衡之后還需要判斷左右兩個子樹是否平衡，這樣樹的高度就會出現(xiàn)重復計算，效率比較差。我們可以換一種思路，從下往上判斷。
當計算二叉樹高度的時候，從下往上如果子樹已經(jīng)出現(xiàn)了不平衡，不要返回二叉樹的高度，返回 -1 即可。計算的時候如果子樹有返回 -1 的，說明子樹已經(jīng)出現(xiàn)了不平衡，就不需要在計算了，否則就返回二叉樹的高度。
JAVA：
public boolean isBalanced(TreeNode root) { return depth(root) != -1; } // 計算二叉樹的高度，如果返回了 -1 ，說明出現(xiàn)了不平衡。 private int depth(TreeNode root) { if (root == null) return0; int left = depth(root.left);// 計算左子樹的高度 int right = depth(root.right);// 計算右子樹的高度 // 如果左右子樹只要有一個返回 -1 ，說明子樹出現(xiàn)了不平衡， // 否則如果左右子樹高度差的絕對值大于 1 ，也說明出現(xiàn)了不平衡。 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 ，說明出現(xiàn)了不平衡。 int depth(TreeNode *root) { if (root == nullptr) return0; int left = depth(root->left);// 計算左子樹的高度 int right = depth(root->right);// 計算右子樹的高度 // 如果左右子樹只要有一個返回 -1 ，說明子樹出現(xiàn)了不平衡， // 否則如果左右子樹高度差的絕對值大于 1 ，也說明出現(xiàn)了不平衡。 if (left == -1 || right == -1 || abs(left - right) > 1) return-1; return1 + max(left, right);// 否則返回二叉樹的高度 }筆者簡介
博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數(shù)據(jù)結構和算法 的講解，在全球30多個算法網(wǎng)站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。
熱門跟貼