DAY 21
1
Software Development

## [Day 21] 從LeetCode學演算法 - 0110. Balanced Binary Tree (Easy)

``````Question:
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.
``````
``````Example 1:
Given the following tree [3,9,20,null,null,15,7]:
3
/ \
9  20
/  \
15   7
Return true.
``````
``````Example 2:
Given the following tree [1,2,2,3,3,null,null,4,4]:
1
/ \
2   2
/ \
3   3
/ \
4   4
Return false.
``````

1. 二元樹的左子樹是平衡的
2. 二元樹的右子樹是平衡的
3. 二元樹的左右子樹高的差不大於1
對於一個樹的高度(或稱作深度)，
是指從樹的根節點走到葉節點的最大長度，所以基於這點，
我們的流程應該是從根節點往下，
檢查以每個節點為基準的左右子樹高的差均不大於1，
該二元樹即為平衡的，反之則為不平衡。

``````maxdp(root) {
if root == NIL return 0
l = maxdp(root.left)
r = maxdp(root.right)
return max(l, r) + 1
}
``````

(+1是因為經過了自己這個節點)

``````let res = true
maxdp(root) {
if (root == NIL or !res) return 0
l = maxdp(root.left)
r = maxdp(root.right)
if (abs(l-r) > 1) {
res = false
return 0
}
return max(l, r) + 1
}
``````

Java:

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean res = true;
public boolean isBalanced(TreeNode root) {
maxdp(root);
return res;
}
public int maxdp(TreeNode root) {
if (root == null || !res) return 0;
int l = maxdp(root.left);
int r = maxdp(root.right);
if (Math.abs(l-r) > 1) {
res = false;
return 0;
}
return Math.max(l, r) + 1;
}
}
``````

Python這邊展示了一個再進一步的思路：

Python:

``````# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def isBalanced(self, root: TreeNode) -> bool:
def check(root):
if root is None:
return 0
left  = check(root.left)
right = check(root.right)
if left == -1 or right == -1 or abs(left - right) > 1:
return -1
return 1 + max(left, right)

return check(root) != -1
``````

「時間/空間複雜度？」
(最差狀況是樹很平衡，每一層都要檢查，時間複雜度是O(N)

0062. Unique Paths (Medium)

### 1 則留言

0
ichiroit
iT邦新手 5 級 ‧ 2021-05-29 11:44:49

(最差狀況是樹很平衡，每一層都要檢查，時間複雜度是O(N)

``````> left  = check(root.left)
> right = check(root.right)
> if left == -1 or right == -1 or abs(left - right) > 1:
>     return -1
``````

``````left  = check(root.left)
if left == -1:
return -1

right = check(root.right)
if right == -1:
return -1

if abs(left - right) > 1:
return -1
``````

Desolve iT邦新手 5 級 ‧ 2021-05-30 02:48:35 檢舉

ichiroit iT邦新手 5 級 ‧ 2021-05-30 17:15:06 檢舉