[Golang][Leetcode][BinaryTree]刷題系列-110-Balanced Binary Tree

Contents
110. Balanced Binary Tree
Level : Easy
原題連結 : Click
題目 :
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 left and right subtrees of every node differ in height by no more than 1.
Example :
Note
Example 1:
Input: root = [3,9,20,null,null,15,7] Output: true
Example 2:
Input: root = [1,2,2,3,3,null,null,4,4] Output: false
Example 3:
Input: root = [] Output: true
解題思路 :
- 這題雖然難度為easy但其實還是需要細細思考才能掌握裡面的邏輯!
- 首先先了解題目的問題,題目需要我們找判斷該 binary tree 是否為 balanced tree
- 題目給balanced tree的定義是一個binary tree他的 left and right subtree的height之間不能差超過1,然後每一個subtree都是balanced tree
- 我們可以先就單一方面去想,先定義如何找到the height of tree的function,在這個function中,我們勢必要比較該tree的left subtree 與 right subtree 的 height誰比較大,這有點 dynamic programming的感覺,每一個最小單位的最佳解組合起來就是該問題的最佳解,這邊也一樣,每一個最小單位的max height subtree組起來就是max height subtree,這個觀念可以從 height , maxHeight function中觀察到
- 之後比subtree之間height的差值,若大於1,就可以直接結束程式,return false,反之則繼續做下去,對每一個node(每一個subtree)都做isBalanced function
Recursive解法
- time complexity: O(n) , space complexity: O(1)
|
|
最後祝福努力認真的各位 “All your dream of are hidden in your daily life” 我們峰頂見!!!