寒假每日提升(4)[对于二叉树类的简单问题]

本文介绍: 在这篇文章中我简单的介绍了二叉树的定义和一些简单的性质，其中最最重要的，其实我觉得应该是那句话，因此，二叉树是由递归定义的，这句话大大的影响着后面我们解题时候的想法。也需要我们很好的认识和理解递归在解题时的运用。到这里，对于基本的二叉树相关的问题已经解决的，差不多了，在寒假继续进行中，我将继续更新关于二叉树的更深的题目，以及未来的堆类的介绍和相关的问题。大家多多关注。我会逐步更新的。

顽强的毅力可以征服世界上任何一座高峰。 ——狄更斯

在这篇文章中我简单的介绍了二叉树的定义和一些简单的性质，其中最最重要的，其实我觉得应该是那句话，因此，二叉树是由递归定义的，这句话大大的影响着后面我们解题时候的想法。也需要我们很好的认识和理解递归在解题时的运用。

对于二叉树来说，并不是所有的二叉树都是满二叉树或完全二叉树，也有些二叉树是特例独行的，那么我们该怎么去计算对于普通的二叉树的最大高度呢？将一个个节点的左右深度进行对比。那么又怎么求得左右深度呢？==那我们就先求根节点左右子树，以左右子树为根的深度，怎么求得左右子树的深度呢？那我们就求左右子树的左右节点的子树的深度。当到最后的时候，左右子树都是空，那么开始返回，返回1，进行比较。然后比较出最后的答案。

对于求最大深度的问题，我们可以将大问题化小，运用递归的思想来对上面的问题进行解答。

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};
typedef struct TreeNode TreeNode;
int maxDepth(struct TreeNode* root) 
{
    if(!root)
    return 0;
    int max=maxDepth(root->left);
    int min=maxDepth(root->right);
    if(min>max)
    {
        int m=min;
        min=max;
        max=m;
    }
    return max+1;
}

注意：其中最重要的是在比较一个节点左右两边哪一个是大的之后，一定要return的时候返回max+1，要把自己在的那一层加上。

对于二叉树叶子节点的个数，最重要的找到一个节点，**它的左右子树都是空的节点。**那么我们怎么找呢？那必然也是要通过递归，才能找到的啊。

//叶子节点的个数
int TreeLeafSize(TreeNode* root)
{
    //空 返回0
    if(root==NULL)
    return 0;
    if(!root->left&&!root->right)
    return 1;
    return TreeLeafSize(root->left)+TreeLeafSize(root->right);

TreeNode*TreeFind(TreeNode*root,BTDataType x)
{
     if(root==NULL)
     return NULL;
     if(root->data==x)
     return root;
     TreeNode*ret1=TreeFind(root->left,x);
     if(ret1)
     return ret1;
     TreeNode*ret2=TreeFind(root->right,x);
     return ret2;
     return NULL;
}

int TreeLevelK(TreeNode*root,int k)
{
    assert(k>0);
    if(root==NULL)
    return 0;
    if(k==1)
    return 1;
    return TreeLevelK(root->left)+TreeLevelK(root->right);
}

bool isSameTree(struct TreeNode*p,struct TreeNode*q)
{   //两个同时为空
    if(!p&&!q)
    return true;
    //有一个不为空
    if(!p||!q)
    return false;
    if(p->val!=q->val)
    return false;
    return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);

bool _isSymmetric(struct TreeNode*root1,struct TreeNode*root2)
{
     if(root1==NULL&&root2==NULL)
     return true;
     if(!root1||!root2)
     return false;
     if(root1->val!=root2->val)
     return false;
     return _isSymmetric(root1->left,root2->left)&&_isSymmetric(root1->right,root2->right);