你的位置:首页 > Java教程

[Java教程]110. Balanced Binary Tree


Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

代码如下:

 1 /** 2  * Definition for a binary tree node. 3  * public class TreeNode { 4  *   int val; 5  *   TreeNode left; 6  *   TreeNode right; 7  *   TreeNode(int x) { val = x; } 8  * } 9 */10 public class Solution {11   12   public boolean isBalanced(TreeNode root) {13    if(root==null)14    return true;15    16    if(DFS(root)==-1)17    return false;18    19    return true;20    21   }22   23   public int DFS(TreeNode root){24     int left=1,right=1;25     if(root.left!=null)26     {27       if(DFS(root.left)==-1)28       return -1;29       else30       left=left+DFS(root.left);31     }32     if(root.right!=null)33     {34       if(DFS(root.right)==-1)35       return -1;36       else37       right=right+DFS(root.right);38     }39     40     if(left-right<-1||left-right>1)41     return -1;42     43     return Math.max(left,right);44   }45  46 }