目录
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
int height(struct TreeNode* root) {
if (root == NULL) {
return 0;
} else {
return fmax(height(root->left), height(root->right)) + 1;
}
}
bool isBalanced(struct TreeNode* root) {
if (root == NULL) {
return true;
}
else
{
//递归祖先结点的整个左子树的左右子树并计算整个左子树的深度、以及整个右子树的左右子树并计算整个左右子树的深度
//由于一颗二叉树是平衡二叉树，则它的所有子树也都是平衡二叉树
return fabs(height(root->left) - height(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
}
}????????首先要知道的是，一颗树是否为平衡二叉树在于它的左右子树的高度查是否为1，我们首先利用递归宏观的计算整棵树的左子树和右子树的高度差，height函数中fmax函数的作用就是选出当前结点的左右子树的最大深度，然后加一得到当前结点及其左右子树的整体高度，然后将该高度返回，fabs函数计算的是整棵树左右子树的高度差的绝对值，如果该绝对值小于等于1那么宏观上看该树是一颗平衡二叉树，但是微观上我们无法保证，所以在使用fabs函数后还需要递归判断整棵树的左右子树是否是一颗平衡二叉树，它们的子树是否是一颗平衡二叉树......（平衡二叉树的所有子树均为平衡二叉树）
时间复杂度：O（N^2）（n是二叉树中的节点个数，且二叉树为链式结构(一条线)，高度为n，n*n）
空间复杂度：O（N）（?n是二叉树中的节点个数，空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过n）
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
int height(struct TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftHeight = height(root->left);
int rightHeight = height(root->right);
if (leftHeight == -1 || rightHeight == -1 || fabs(leftHeight - rightHeight) > 1) {
return -1;
} else {
return fmax(leftHeight, rightHeight) + 1;
}
}
//因为自底向上的判断过程中，如果某一节点不满足平衡条件，那么该节点向上层父节点返回-1，上层结点如果发现自己的左右结点有一个为-1，就表示它知道这棵树不是平衡二叉树，自己也就不再判断而直接再次向自己的上层结点返回-1，所以最后根结点直接判断是不是大于零就行，因为如果不是平衡二叉树最后根节点会返回-1.
bool isBalanced(struct TreeNode* root) {
return height(root) >= 0;
}
????????根据height函数的返回值判断是否是平衡二叉树，在height函数中，我们先递归完左子树到头时返回0并将该值用leftHeight接收，然后递归当前结点的右子树如果也为空则返回0，然后判断leftHeight和rightHeight以及它俩的差值的绝对值是否大于一，一般来说该判断语句第一次结果为真都是因为差值绝对值大于一，然后才会返回-1，导致leftHeight或者rightHeight值为-1，然后-1会一直传递直到整个递归结束，它标志着该二叉树不是平衡二叉树，当该判断语句为假时就会利用fmax函数计算当前结点作为一棵树时的高度，如果该树不是平衡二叉树就会导致，该高度会一直叠加从而第一次触发fabs函数，然后就整体递归调用返回-1，该树不为平衡二叉树
时间复杂度：O（N）（n是二叉树中的节点个数，每个节点的计算高度和判断是否平衡都只需要处理一次）
空间复杂度：O（N）（?n是二叉树中的节点个数，空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过n）
????????自顶向下的看着很美，细看由于没有记录结点，存在子序列重复的情况。主函数内return封住了当前为平衡点以及左右子结点为平衡点，可是每次递归都会重复对尾部到当前的第n-1高度结点重复判断，导致了 n(1+n)/2, 效率太低。所以还得是自下向上，省去了记忆化过程，天然回溯到父节点就可以得到子节点的高度
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode* invertTree(struct TreeNode* root) {
if (root == NULL) {
return NULL;
}
struct TreeNode* left = invertTree(root->left);
struct TreeNode* right = invertTree(root->right);
root->left = right;
root->right = left;
return root;
}
????????由于二叉树是链式结构的，所以更改父亲结点的同时，该父亲结点的子孙结点都会跟着移动，所以这里我们利用递归，分别将两个要翻转的两颗子树的左右子树进行翻转，然后在递归返回地过程中将两个树地父亲结点也翻转，这样就完成了一次二叉树地翻转
时间复杂度：O（N）（n是二叉树中的节点个数，使用自底向上的递归，每个节点的计算高度和判断是否平衡都只需要处理一次，最坏情况下需要遍历二叉树中的所有节点）
空间复杂度：O（N）（?n是二叉树中的节点个数，空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过n）
~over~