110. 平衡二叉树
?做题思路or感想:
-
用递归后序遍历二叉树,然后从底部开始记录高度为0,然后往上加1。
-
每一次操作节点的时候比较左右子树的高度,如果有一棵树不符合条件,则直接把-1返回到最顶的根节点
-
class Solution { public: int getDepth(TreeNode* cur) { if (cur == nullptr)return 0; //节点触底后,从高度为0开始计数 //检验左右子树是否符合条件 int leftDepth = getDepth(cur->left); if (leftDepth == -1) return -1; int rightDepth = getDepth(cur->right); if (rightDepth == -1)return -1; if (abs(leftDepth - rightDepth) > 1)return -1; else { //若符合条件,则往上+1 return max(leftDepth, rightDepth) + 1; } } bool isBalanced(TreeNode* root) { if (getDepth(root) != -1)return true; else return false; } };