https://www.nowcoder.com/practice/8b3b95850edb4115918ecebdf1b4d222?tpId=13&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking

题目描述

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树

代码

左子树和右子树高度差不得超过1 即为平衡二叉树;

  1. public class Solution {
  2.   public boolean IsBalanced_Solution(TreeNode root) {
  3.         if (root == null) {
  4.             return true;
  5.         }
  6.         int left=depth(root.left);
  7.         int right=depth(root.right);
  8.         int diff=Math.abs(left-right);
  9.         if (diff>1){
  10.             return false;
  11.         }
  12.         return IsBalanced_Solution(root.left)&&IsBalanced_Solution(root.right);
  13.     }
  15.     private int depth(TreeNode root) {
  16.         if (root == null) {
  17.             return 0;
  18.         }
  19.         int left = depth(root.left);
  20.         int right = depth(root.right);
  21.         return Math.max(left, right) + 1;
  22.     }
  24. }
  1. class Solution {
  2. public:
  3.     bool IsBalanced_Solution(TreeNode *pRoot) {
  4.         if (pRoot == nullptr) {
  5.             return true;
  6.         }
  7.         int left = depth(pRoot->left);
  8.         int right = depth(pRoot->right);
  9.         if (abs(left - right) > 1) {
  10.             return false;
  11.         }
  12.         return IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right);
  13.     }
  15. public:
  16.     int depth(TreeNode *root) {
  17.         if (root == nullptr) {
  18.             return 0;
  19.         }
  20.         int left = depth(root->left);
  21.         int right = depth(root->right);
  22.         return max(left, right) + 1;
  23.     }
  24. };