JZ79 判斷是不是平衡二叉樹
描述
輸入一棵節點數為 n 二叉樹，判斷該二叉樹是否是平衡二叉樹，
在這里，我們只需要考慮其平衡性，不需要考慮其是不是排序二叉樹
平衡二叉樹（Balanced Binary Tree），具有以下性質：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹，
思路
左右兩個子樹的高度差的絕對值不超過1
左右兩個子樹都是一棵平衡二叉樹
代碼
package esay.JZ79判斷是不是平衡二叉樹;
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public class Solution {
//自頂向下
/*public boolean IsBalanced_Solution(TreeNode root) {
//空樹也是平衡二叉樹
if (root == null) return true;
//左子樹深度
int left = deep(root.left);
//右子樹深度
int right = deep(root.right);
if (left - right > 1 || right - left > 1) return false;
return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
}
public int deep (TreeNode node) {
if (node == null) return 0;
//左遍歷
int left = deep(node.left);
//右遍歷
int right = deep(node.right);
return left > right ? left + 1 :right + 1;
}*/
//自底向上
public boolean IsBalanced_Solution(TreeNode root) {
if (root == null) return true;
return getdepth(root) != -1;
}
public int getdepth (TreeNode node) {
if (node == null) return 0;
//左遍歷
int left = getdepth(node.left);
if (left < 0) return -1;
//右遍歷
int right = getdepth(node.right);
if (right < 0) return -1;
return Math.abs(left - right) > 1 ? -1 : Math.max(left, right) + 1;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/536788.html
標籤：Java