劍指 Offer 55 - II. 平衡二叉樹 - leetcode 劍指offer系列

2020-08-28 每日精選算法題

題目難度: 簡單

原題連結[1]

今天繼續更新劍指 offer 系列, 老樣子晚上 6 點 45 分準時更新公眾號 每日精選算法題, 大家記得關注哦~ 另外在公眾號裡回復 offer 就能看到劍指 offer 系列當前連載的所有文章了

題目描述

輸入一棵二叉樹的根節點，判斷該樹是不是平衡二叉樹。如果某二叉樹中任意節點的左右子樹的深度相差不超過 1，那麼它就是一棵平衡二叉樹。

  • 1 <= 樹的結點個數 <= 10000

題目樣例

示例

給定二叉樹 [3,9,20,null,null,15,7]    3   / \  9  20    /  \   15   7返回 true 。

給定二叉樹 [1,2,2,3,3,null,null,4,4]       1      / \     2   2    / \   3   3  / \ 4   4返回 false 。

題目思考

  1. 可以只需要遍歷一遍節點得到結果嗎?

解決方案

思路

  • 有了昨天劍指 Offer 55 - I. 二叉樹的深度 - leetcode 劍指 offer 系列的鋪墊, 這道題相信大家都可以迎刃而解
  • 一個比較容易想到的思路是: 先計算出每個節點的深度, 並將其存入節點=>深度字典中; 然後再遍歷一遍節點, 針對每個節點, 判斷它左右子節點的深度是否滿足要求, 所有節點都滿足的話才說明平衡. 但是這種方案需要遍歷兩邊節點, 效率不太高, 如何一次性遍歷得出結果呢?
  • 回顧遞歸求深度的方案, 我們是先求得左右子樹的深度, 然後才進一步得到當前節點的深度, 所以我們就可以直接加一個全局變量記錄當前是否平衡, 並額外引入一個邏輯來比較子樹深度, 如果不滿足要求, 則直接把變量置為 false 直接返回即可
  • 注意本題並不適用於 BFS 迭代求深度的算法, 因為迭代方案求的是當前節點從上到下所在的層數, 每個節點並不知道自己的深度(從下往上, 從葉子節點到自身)究竟是多少, 所以無從判斷是否平衡
  • 下面代碼對必要的步驟有詳細的解釋, 方便大家理解

複雜度

  • 時間複雜度 O(N): 需要遍歷整個樹
  • 空間複雜度 O(H): H 表示樹的高度, 也即遞歸的棧的消耗

代碼

class Solution:    def isBalanced(self, root: TreeNode) -> bool:         遞歸出口: 如果節點為空或者不平衡, 返回0, 無需繼續遞歸了                return 0            ldepth = getDepth(node.left)            rdepth = getDepth(node.right)            if abs(ldepth - rdepth) > 1:                 返回當前節點自身的深度            return max(ldepth, rdepth) + 1        getDepth(root)        return balance

參考資料

[1]

原題連結: https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/

相關焦點

  • 劍指 Offer 58 - I. 翻轉單詞順序 - leetcode 劍指offer系列
    題目難度: 簡單原題連結[1]今天繼續更新劍指 offer 系列, 老樣子晚上 6 點 45 分準時更新公眾號 每日精選算法題, 大家記得關注哦~ 另外在公眾號裡回復 offer 就能看到劍指 offer 系列當前連載的所有文章了題目描述輸入一個英文句子，翻轉句子中單詞的順序，但單詞內字符的順序不變。
  • (二叉樹)
    「注意這個周末總結和系列總結還是不一樣的（二叉樹還遠沒有結束），這個總結是針對留言疑問以及刷題群裡討論內容的歸納。」周一本周我們開始講解了二叉樹，在關於二叉樹，你該了解這些！中講解了二叉樹的理論基礎。周二在二叉樹：一入遞歸深似海，從此offer是路人中講到了遞歸三要素，以及前中後序的遞歸寫法。
  • 調整數組順序使奇數位於偶數前面(劍指 Offer 題解,面試)
    package 劍指offer.調整數組順序使奇數位於偶數前面_21;/*作者 :XiangLin文件 :OrderArray.javaIDE :IntelliJ IDEA*/import java.util.Arrays;public class OrderArray {
  • 春節大禮包|刷題技巧+80道Leetcode
    為了跳槽，我前兩年的春節都是在刷題中度過的，目前為止刷了小四百道leetcode，也算是有一些經驗，今天就跟大家分享下學習方法和我總結的乾貨。如何找到感覺講起算法，我看過不少書，有《算法導論》、《算法第四版》、《算法競賽入門經典》、《劍指Offer》，但都沒有讓我產生質變，現在回想原因可能是：看書的時候著急，不過腦子直接看解析，也不記筆記，過幾天就忘了看完書就覺得自己會了，直接 Leetcode 隨機選題，還是不會，內心受挫就不想刷了
  • 劍指offer python實現 66道算法題
    17.樹的子結構題目：輸入兩棵二叉樹A，B，判斷B是不是A的子結構。24.二叉樹中和為某一值的路徑題目：輸入一顆二叉樹和一個整數，列印出二叉樹中結點值的和為輸入整數的所有路徑。路徑定義為從樹的根結點開始往下一直到葉結點所經過的結點形成一條路徑。
  • 平衡二叉樹專題
    力扣關於平衡二叉樹的題目還是有一些的，並且都非常經典，推薦大家練習。今天給大家精選了 4 道題，如果你徹底搞明白了這幾道題，碰到其他的平衡二叉樹的題目應該不至於沒有思路。當你領會了我的思路之後， 建議再找幾個題目練手，鞏固一下學習成果。110.
  • 一文讀懂平衡二叉樹|技術頭條
    作者 | 宋廣澤責編 | 伍杏玲出品 | CSDN(ID：CSDNnews)平衡二叉樹，又稱AVL樹，指的是左子樹上的所有節點的值都比根節點的值小，而右子樹上的所有節點的值都比根節點的值大，且左子樹與右子樹的高度差最大為1。因此，平衡二叉樹滿足所有二叉排序（搜索）樹的性質。
  • 深入理解樹(二叉、二叉搜索樹)
    （B的高度為2，B—F—J）；樹的高度：是樹中所有結點高度的最大值，樹的深度是樹中所有結點深度的最大值，對於同一棵樹，其深度和高度是相同的，但是對於各個結點，其深度和高度不一定相同；二叉樹如果一棵樹中的每個結點有0，1或者2個孩子結點，那麼這棵樹就稱為二叉樹；空樹也是一顆有效的二叉樹，一顆二叉樹可以看做是由根節點和兩棵不相交的子樹
  • 幾道和「二叉樹」有關的算法面試題
    例如:給定二叉樹: [3,9,20,null,null,15,7],    3   / \  9  20    /  \   15   7返回其層次遍歷結果：[  [3],  [9,20],  [15,7]]題目解析 該問題需要用到
  • 什麼是平衡二叉樹(AVL)
    1 為什麼要有平衡二叉樹二叉搜索樹一定程度上可以提高搜索效率，但是當原序列有序時，例如序列 A = {1，2，3，4，5，6}，構造二叉搜索樹如圖 1.1。依據此序列構造的二叉搜索樹為右斜樹，同時二叉樹退化成單鍊表，搜索效率降低為 O(n)。圖 1.1在此二叉搜索樹中查找元素 6 需要查找 6 次。
  • 數據結構(八)--平衡二叉樹
    儘量將其調整為滿二叉樹形式或者向滿二叉樹靠近，但是滿二叉樹對每層的節點個數都有固定要求，如果單純的就是調整為滿二叉樹也不現實。所以我們要將二叉樹儘量調整為左右子樹高度差最多不超過1的平衡二叉樹。這也就是平衡二叉樹的作用了。所以，接下來為了避免二叉樹的退化，我們需要明白二叉樹什麼時候需要調整，要怎麼調整。
  • 數據結構 | 四種平衡二叉樹介紹
    同時，本文也進一步探討研究了較常使用的平衡二叉樹和六種不同的平衡二叉樹的性能並對其做了對比分析，為未來計算機應用提供了可供參考的意見。1.2  平衡二叉搜索樹（BBST）由於二叉搜索樹在最壞情況下可能退化為列表，此時的各種效率降至O(n)。因此如果不能有效的控制樹高，二叉搜索樹無法體現出明顯的優勢。因此，需要依照某種寬鬆的標準，重新定義二叉搜索樹的平衡性。
  • 程式設計師面試必備《劍指Offer》PDF免費分享
    《劍指Offer》是2012年電子工業出版社出版的圖書，作者是何海濤。本書精選谷歌、微軟等知名IT企業的50餘道典型面試題，系統地總結了如何在面試時寫出高質量代碼，如何優化代碼效率，以及分析、解決難題的常用方法。
  • 14種模式搞定面試算法編程題(PART II)
    面試錦囊系列一直有收到大家的反饋，包括後臺內推成功的消息、朋友的同事從創業小公司成功跳到huawei等等，非常高興小破號的這些整理分享能夠真正地幫助到大家leetcode-cn.com/problems/find-the-duplicate-number/[3]缺失的第一個正數（LEETCODE）: https://leetcode-cn.com/problems/first-missing-positive/[4]反轉鍊表（LEETCODE）: https://leetcode-cn.com/problems/reverse-linked-list
  • 刷題兩個月,從入門到字節跳動offer,這是我的模板|GitHub1.2k星
    第三步，劍指offer劍指offer基本上是大部分公司的出題源頭，刷題面試中基本會遇到現題或者變形題，刷完這三部分，大部分國內公司的面試題應該都沒有問題了。另外，作者還溫馨提示：刷題時間要合理分配。如果打算準備面試了，建議前面兩部分，一個半月（6周）的時間刷完，最後劍指offer半個月刷完，邊刷可以邊投簡歷進行面試，遇到不會的，往模版上套就對了。練習題內容既然練習題那麼重要，那麼我們就來搶先來了解一下～核心內容主要分為四個部分。
  • 校招offer:本碩機械轉大數據開發
    先上幾張他跟我聊天的一些內容，從心虛、懷疑到拿到心儀的offer4月30號，通過知乎文章加了我的微信5月份，背面試題到懷疑人生，哈哈哈（原諒我笑出了聲，體會到我當年的痛苦，哈哈哈哈）>九月底也算是拿到了某上市公司 offer。
  • LeetCode-117.填充每個節點的下一個右側節點指針 II(Populating Next Right Point...)
    填充每個節點的下一個右側節點指針 II給定一個二叉樹struct Node { int val; Node *left; Node *right; Node *next;}填充它的每個next指針，讓這個指針指向其下一個右側節點。
  • 五分鐘帶你玩轉平衡二叉樹
    通過上一篇二叉查找樹的文章，相信大家已經掌握了二叉查找樹的相關概念和操作，如果忘了可以通過下方的連結進行學習。帶你玩轉二叉查找樹本文呢，我們將在二叉查找樹的基礎上，繼續學習一種新的樹狀結構-平衡二叉樹。
  • 熱乎的宇宙條總部面經,已拿offer,速來圍觀
    1、 3月24日 抖音後端這一天，我迎來了我在字節跳動的第一場面試雖然有對實習頂目有做過梳理，可能還是對一些細節思考的深度不夠，回答的還是磕磕絆絆的頂目講完了就開始上算法題了題目是劍指offer原題--棧旋轉數組的中位數當時是記得有做過求旋轉數組的最小值，所以知道大概是用二分法去做
  • 每日一道 LeetCode (21):對稱二叉樹
    前文合集每日一道 LeetCode 前文合集代碼倉庫GitHub：https://github.com/meteor1993/LeetCodeGitee：https://gitee.com/inwsy/LeetCode題目：對稱二叉樹