我的LeetCode：https://leetcode-cn.com/u/ituring/
我的LeetCode刷題原始碼[GitHub]：https://github.com/izhoujie/Algorithmcii
LeetCode 110. 平衡二叉樹
題目
給定一個二叉樹，判斷它是否是高度平衡的二叉樹，
本題中，一棵高度平衡二叉樹定義為：
- 一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過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-自頂向下，遞回校驗
遞回計算同層節點左右子樹的高度差，存在重復計算；
演算法復雜度:
- 時間復雜度： $ {\color{Magenta}{\Omicron\left(nlogn\right)}} $ 計算略復雜：詳見復雜度分析
- 空間復雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $ 遞回堆疊的深度
思路2-自底向上/二叉樹的后序遍歷，遞回校驗
與方法1的唯一區別是從葉子節點開始向上校驗同層節點的左右子樹高度差，一旦發現差超過1的可以直接回傳，跳過對上層節點的計算，速度最快；
演算法復雜度:
- 時間復雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $ 每個節點最多訪問一次
- 空間復雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $ 遞回堆疊的深度
演算法原始碼示例
package leetcode;
/**
* @author ZhouJie
* @date 2020年1月11日 下午8:32:42
* @Description: 110. 平衡二叉樹
*
*/
public class LeetCode_0110 {
}
// Definition for a binary tree node.
class TreeNode_0110 {
int val;
TreeNode_0110 left;
TreeNode_0110 right;
TreeNode_0110(int x) {
val = x;
}
}
class Solution_0110 {
/**
* @author: ZhouJie
* @date: 2020年5月18日 下午11:54:54
* @param: @param root
* @param: @return
* @return: boolean
* @Description: 1-對根及左右子樹遞回計算高度差；
*
*/
public boolean isBalanced_1(TreeNode_0110 root) {
// 當前節點為null或者其左右節點的高度差不大于1
return root == null || isBalanced_1(root.left) && isBalanced_1(root.right)
&& Math.abs(maxDepth(root.left) - maxDepth(root.right)) < 2;
}
/**
* @author: ZhouJie
* @date: 2020年5月19日 上午11:54:20
* @param: @param root
* @param: @return
* @return: int
* @Description: 計算樹高
*
*/
private int maxDepth(TreeNode_0110 root) {
return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
/**
* @author: ZhouJie
* @date: 2020年5月18日 下午11:55:37
* @param: @param root
* @param: @return
* @return: boolean
* @Description: 2-后續遍歷，自底向上校驗每層樹的高度差，一旦不平衡直接回傳，上層節點不再處理；
*
*/
public boolean isBalanced_2(TreeNode_0110 root) {
return checkBlance(root) != -1;
}
private int checkBlance(TreeNode_0110 root) {
if (root == null) {
return 0;
}
// 遞回計算左右子樹的高度，若遇到-1代表樹已在某一層已經不平衡，無需再遞回了，直接回傳
int left = checkBlance(root.left);
if (left == -1) {
return -1;
}
int right = checkBlance(root.right);
if (right == -1) {
return -1;
}
// 一旦任意同層左右子樹的高度差大于1就直接回傳-1，-1會直接回傳，相當于剪枝，避免后面無意義的遞回
return Math.abs(left - right) > 1 ? -1 : Math.max(left, right) + 1;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/189838.html
標籤：Java