LeetCode刷题(9)【树】前序&深度&平衡(C语言)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 //计算结点个数
 int TreeSize(struct TreeNode* root)
 {
     return root == NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
 }
 //前序遍历
void _preorder(struct TreeNode* root,int* a,int *i)//为了保证一直对一个i进行操作所以要传地址
{
    if(root == NULL)
    {
        return ;
    }
    a[*i] = root->val;
    (*i)++;
    _preorder(root->left,a,i);
    _preorder(root->right,a,i);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize){
     int size = TreeSize(root);
     //创建数组
     int* a = (int*)malloc(size*sizeof(int));
     int i = 0;
     _preorder(root,a,&i);
     *returnSize = size;
     return a;
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


int maxDepth(struct TreeNode* root){
    if(root == NULL)
        return 0;
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);

    return leftDepth > rightDepth?leftDepth+1:rightDepth+1;
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int maxDepth(struct TreeNode* root){
    if(root == NULL)
        return 0;
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);

    return leftDepth > rightDepth?leftDepth+1:rightDepth+1;
}

bool isBalanced(struct TreeNode* root){
    //空树也满足条件
    if(root == NULL)
    {
        return true;
    }
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);
    //如果一开始就不满足就没必要往下进行了，满足就递归判断左右
    return abs(leftDepth-rightDepth) < 2
    && isBalanced(root->left)
    && isBalanced(root->right);                                          
}