LeetCode--Balanced Binary Tree

超、凢脫俗 2022-08-18 00:53 86阅读 0赞

Problem:

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.

Analysis:
题意:
给定的二进制树,确定它是否是均衡二叉树。
对于这个问题,一个高度平衡二叉树被定义为一种二叉树,其中各节点的两个子树的深度相差不能超过1。
Anwser:

  1. public class Solution {
  2. public boolean isBalanced(TreeNode root) {
  3. if(root==null) return true;
  4. //下面两行可以改为return depth(root)!=-1;
  5. if(depth(root)!=-1) return true;
  6. else return false;
  7. }
  8. public int depth(TreeNode root){
  9. if(root==null) return 0;
  10. int ldep,rdep;
  11. ldep = depth(root.left);
  12. rdep = depth(root.right);
  13. //-----这两行是比求树的高度多出的代码,从这里多加一层判断来满足要求。-----//
  14. if(ldep==-1 || rdep==-1) return -1;
  15. if(Math.abs(ldep-rdep)>1) return -1;
  16. //-------------------------------------------------------------//
  17. else {
  18. return Math.max(ldep,rdep)+1;
  19. }
  20. }
  21. }

发表评论

表情:
评论列表 (有 0 条评论,86人围观)

还没有评论,来说两句吧...

相关阅读