LeetCode--Balanced Binary Tree

超、凢脫俗 2022-08-18 00:53 104阅读 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.     }
  22. }

发表评论

表情：
评论列表 （有 0 条评论，104人围观）

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

相关阅读