給定一個二叉樹，判斷它是否是高度平衡的二叉樹，
本題中，一棵高度平衡二叉樹定義為：
一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過1，
示例 1:
給定二叉樹 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
回傳 true ，
示例 2:
給定二叉樹 [1,2,2,3,3,null,null,4,4]
1
/ \
2 2
/ \
3 3
/ \
4 4
回傳 false ，
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/balanced-binary-tree
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
解法1：
根據定義，一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過1，很容易想到，判斷一個平衡二叉樹的條件
- 左右子樹是平衡二叉樹
- 左右子樹高度差不超過1
func isBalanced(root *TreeNode) bool {
// 空樹是平衡二叉樹，遞回出口
if (root == nil) {
return true
}
// 左右子樹高度差不超過1，且左右子樹都是平衡二叉樹
return abs(height(root.Left) - height(root.Right)) <=1 && isBalanced(root.Left) && isBalanced(root.Right)
第二個問題，如何求樹的高度？
樹的高度由左右子樹的高度確定
func height(root *TreeNode) int {
if (root == nil) {
return 0
}
return max(height(root.Left), height(root.Right)) + 1
}
優化
上面的解法在計算height的時候會重復呼叫，時間復雜度是O(n^2)，可以使用自底向上的方法，對于每個節點，height只計算一次
func height(root *TreeNode) int {
if (root == nil) {
return 0
}
lh := height(root.Left)
rh := height(root.Right)
// 左右子樹不是平衡二叉樹，或高度差大于1，說明該樹不是平衡二叉樹
if (lh == -1 || rh == -1 || abs(lh - rh) > 1) {
return -1
}
return max(lh, rh) + 1
}
func isBalanced(root *TreeNode) bool {
return height(root) >= 0
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/2189.html
標籤：其他