##題目描述 輸入一棵二叉樹，判斷該二叉樹是否是平衡二叉樹，
思路
深度搜索，剪枝，
時間復雜度O(lgn)，空間復雜度O(lgn)，
未剪枝代碼
public class Solution {
private int depth(TreeNode root) {
return root == null ? 0 : Math.max(1+depth(root.left), 1+depth(root.right));
}
public boolean IsBalanced_Solution(TreeNode root) {
return root == null ? true : Math.abs(depth(root.left) - depth(root.right)) <= 1;
}
}
剪枝代碼
public class Solution {
private int depth(TreeNode root) {
if(root == null) return 0;
int left = depth(root.left);
if(left == -1){
return -1;
}
int right = depth(root.right);
if(right == -1) {
return -1;
}
return Math.abs(left-right) < 2 ? 1 + Math.max(left, right) : -1;
}
public boolean IsBalanced_Solution(TreeNode root) {
return depth(root) != -1;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/83482.html
標籤：其他
上一篇：二叉樹的深度
下一篇：陣列中只出現一次的數字