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 ...
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 }
原标题:110. Balanced Binary Tree
关键词:
*特别声明:以上内容来自于网络收集,著作权属原作者所有,如有侵权,请联系我们:
admin#shaoqun.com
(#换成@)。