LeetCode110. 平衡二叉树

平衡二叉树定义：|左子树高度-右子树高度| <= 1
踩坑点：
不能通过根节点的左右子树高度来直接判断是否为平衡二叉树，e.g:假如根节点左子树为左斜树，右子树为右斜树，且两棵子树个数相同，此时根节点左右子树高度相同，但不是平衡二叉树。
因此还是需要一层层地往下判断

1. class Solution {
2. public:
3.     int max(int a, int b)
4.     {
5.         return a > b ? a : b;
6.     }
7.     int getHeight(TreeNode* root)
8.     {
9.         if (root == nullptr) return 0;
10.         int leftHeight = getHeight(root->left);
11.         int rightHeight = getHeight(root->right);
12.         return max(leftHeight, rightHeight) + 1;
13.     }
14.     bool isBalanced(TreeNode* root)
15.     {   
16.         bool res;
17.         if (root == nullptr) return true;
19.         int leftHeight = getHeight(root->left);
20.         int rightHeight = getHeight(root->right);
21.         if (abs((leftHeight - rightHeight)) <= 1)
22.         {
23.             if(!isBalanced(root->left)) return false;
24.             if(!isBalanced(root->right)) return false;
25.             return true;
26.         }
27.         else
28.             return false;
30.     }
31. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。