题目描述
输入一棵二叉树，判断该二叉树是否是平衡二叉树。
思路：
比较左右深度，如果差值大于1，则不平衡。
利用后序遍历，避免每次都从头遍历一次。
遍历过程中，当左节点出现不平衡时，也不需要遍历右节点了，剪枝
class Solution
{
public:
int getDepth(TreeNode *
pRoot)
{
if (pRoot ==
NULL)
return 0;
int left = getDepth(pRoot->
left);
if (left == -
1)
return -
1;
int right = getDepth(pRoot->
right);
if (right == -
1)
return -
1;
if (left - right >
1 || left - right < -
1)
return -
1;
else
return max(left, right) +
1;
}
bool IsBalanced_Solution(TreeNode *
pRoot)
{
return getDepth(pRoot) != -
1;
}
};
转载于:https://www.cnblogs.com/ruoh3kou/p/10147813.html
