leetcode练习题 balanced-binary-tree

解题思路

先写出递归求树高的函数，在主要的判断函数中，若该树为空树则返回true，否则判别其左右子树是否平衡，平衡的话求左右子树各自的树高，并判断左右子树的高度差绝对值是否小于等于1，若左右子树不是平衡二叉树则返回false。

代码

#include<math.h>
#include<algorithm>
class Solution {
public:int treeHeight(TreeNode *root){if(root == NULL)return 0;int l = treeHeight(root->left);int r = treeHeight(root->right);return l > r ? (l + 1) : (r + 1);}bool isBalanced(TreeNode *root) {if(root == NULL)return true;if(isBalanced(root->left) && isBalanced(root->right)){int l_h = treeHeight(root->left);int r_h = treeHeight(root->right);int t = (l_h - r_h) >= 0 ? (l_h - r_h) : (r_h - l_h);return t <= 1;}elsereturn false;}
};