题目描述
输入一棵二叉树，判断该二叉树是否是平衡二叉树。
import java.util.*;
public class Solution {
public boolean IsBalanced_Solution(TreeNode root) {
if(root == null) return true;
int left = getDeep(root.left);
int right = getDeep(root.right);
return Math.abs(left - right) <= 1 && IsBalanced_Solution(root.left)&& IsBalanced_Solution(root.right);
}
private int getDeep(TreeNode root) {
if(root == null) return 0;
return Math.max(getDeep(root.left), getDeep(root.right))+1;
}
}非递归
import java.util.*;
public class Solution {
public boolean IsBalanced_Solution(TreeNode root) {
if(root == null) return true;
int left = getDeep(root.left);
int right = getDeep(root.right);
return Math.abs(left - right) <= 1 && IsBalanced_Solution(root.left)&& IsBalanced_Solution(root.right);
}
private int getDeep(TreeNode root) {
if(root == null) return 0;
LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
int deepl = 0,deepr = 0;
TreeNode node = null;
stack.push(root);
while(!stack.isEmpty()) {
node = stack.pop();
if(node.right != null) {
stack.push(node.right);
deepr++;
}
if(node.left != null) {
stack.push(node.left);
deepl++;
}
}
return Math.max(deepl, deepr) + 1;
}
}
