[LeetCode] 110. Balanced Binary Tree

轉自LeetCode

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

<Solution>

這題是要檢查 binary tree 是否是 height-balanced

根據題目定義，如果一個 binary tree 是 height-balanced，則每個子樹也都會是 height-balanced

因此，使用 recursive 的解法來解

• 以當下的 node 為 root，記算左右子樹的高度，看看是否差距小於 1

• 如果差距小於1，再分別檢查以 left node 為 root 的子樹，和以 right node 為 root 的子樹是否也符合條件

code 如下 (參考資料)

不過上面這個解法的平均時間複雜度是O(NlogN)

每個 root 都要往下歷遍每個node來找高度，總共會做 lnN 次

所以可以用 DFS 改良一下寫法，是一種 bottom-up 的想法

• 先用 DFS 走到 leaf node

• 檢查是否是 height-balanced，是的話，回傳高度資訊；不是的話，回傳 -1

• 最後在 root 的地方，確認 DFS 的結果是不是 -1 即可

code 如下(參考資料)
c++

kotlin