Leetcode 110. Balanced Binary Tree
题目链接: Balanced Binary Tree
难度:Easy
题目大意:
判断二叉树是不是深度平衡树。
思路:
思路1 :
求根节点左右子节点的深度,然后按照题意进行判断。再利用递归,对左右子节点进行相同的操作。
思路2 :
参考 高赞回答 ,求左右节点的深度,如果发现子节点不满足题意中平衡二叉树的条件,提前返回false。
代码
思路1代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isBalanced(TreeNode root) {
if(root==null){
return true;
}
int leftDepth=depth(root.left);
int rightDepth=depth(root.right);
if(Math.abs(leftDepth-rightDepth)>1){
return false;
}
return isBalanced(root.left)&&isBalanced(root.right);
}
private int depth(TreeNode root){
if(root==null){
return 0;
}
int left=depth(root.left);
int right=depth(root.right);
return Math.max(left,right)+1;
}
}
思路2代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isBalanced(TreeNode root) {
int depth=helper(root);
return depth!=-1;
}
public int helper(TreeNode root){
if(root==null){
return 0;
}
int left=helper(root.left);
if(left==-1){//如果左子树不是平衡树,直接返回-1,说明不会是平衡树
return -1;
}
int right=helper(root.right);
if(right==-1){
return -1;
}
if(Math.abs(left-right)>1){
return -1;
}
return Math.max(left,right)+1;//树的深度
}
}