LeetCode刷题（115）～平衡二叉树【自顶向下｜自底向上】

题目描述

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

示例 1:

给定二叉树 [3,9,20,null,null,15,7] 3 / \
  9  20 /  \ 15   7
返回 true 。

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
 

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4] 1 / \ 2   2 / \ 3   3
  / \
 4   4
返回 false 。

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
 

解答

Demo（自顶向下）

// 首先判断 根节点是否符合 依次求出左右树的高度进行判断 
// 然后在分别判断以左节点为树 右节点为树是否符合定义
 int height(TreeNode* root) { if(root==NULL) return 0; return max(height(root->left),height(root->right))+1; } bool isBalanced(TreeNode* root) { if(root==NULL) return true; return abs(height(root->right)-height(root->left))<=1&&isBalanced(root->right)&&isBalanced(root->left); }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
 

运行结果

Demo（自底向上）

int height(TreeNode* root) { if(root==NULL) return 0; int  leftnode=height(root->left); int  rightnode=height(root->right); if(leftnode==-1||rightnode==-1||abs(leftnode-rightnode)>1) return -1; else return max(leftnode,rightnode)+1; } bool isBalanced(TreeNode* root) { return height(root)>=0; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
 

题目来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/balanced-binary-tree

文章来源: haihong.blog.csdn.net，作者：海轰Pro，版权归原作者所有，如需转载，请联系作者。

原文链接：haihong.blog.csdn.net/article/details/108340669