判断是否为平衡二叉树-不改变代码模板的写法
平衡二叉树
http://www.nowcoder.com/questionTerminal/8b3b95850edb4115918ecebdf1b4d222
刚来牛客刷题,刷了几题都看到代码模板中的提示称Class Solution的方法不能改,所以我就按照给定的方法写了个递归。主要是把树的深度存放在pRoot->val中。
class Solution { public: bool IsBalanced_Solution(TreeNode* pRoot) { if(pRoot == NULL) return true; bool leftIsB = IsBalanced_Solution(pRoot->left); bool rightIsB = IsBalanced_Solution(pRoot->right); int leftD = pRoot->left == NULL? 0: pRoot->left->val; int rightD = pRoot->right == NULL? 0: pRoot->right->val; if(leftIsB==false || leftIsB==false || abs(leftD-rightD)>1) return false; else{ pRoot->val = leftD > rightD ? leftD + 1 : rightD + 1; return true; } } };