二叉树的深度

输入一颗二叉树的根节点，求该树的深度。从根节点到叶子节点依次经过的节点形成树的一条路径，最长路径的长度为树的深度。

思路：树的高度为max(左子树的高度，右子树的高度)+1.

参考代码：

root@gt:/home/git/Code# ./a.out 
1 2 4 5 7 3 6 
depth:4
root@gt:/home/git/Code# cat treedepth.c 
#include <stdio.h>
#include <stdlib.h>
typedef struct treenode
{
    int value;
    struct treenode* pleft;
    struct treenode* pright;
}TreeNode;

int treedepth(TreeNode* proot)
{
    if(proot == NULL)
        return 0;
    int left = treedepth(proot->pleft);
    int right = treedepth(proot->pright);
    return (left > right)?(left+1):(right+1);
}

TreeNode* core(int* preStart,int* preEnd,int* inStart,int* inEnd)
{
//前序遍历的地一个元素就是根节点
    int rootValue = preStart[0];
    TreeNode* proot = malloc(sizeof(TreeNode));
    proot->value = rootValue;
    proot->pleft = proot->pright = NULL;

//在中序遍历序号中找到根节点的值
    int* rootIn = inStart;
    while(rootIn <= inEnd && *rootIn != rootValue) ++rootIn;

    int leftLen = rootIn - inStart;
    int* leftPreEnd = preStart + leftLen;

    if(leftLen>0)
    {
        proot->pleft = core(preStart+1,leftPreEnd,inStart,inStart+leftLen-1);
    }
    if(leftLen < preEnd - preStart)
    {
        proot->pright = core(leftPreEnd+1,preEnd,rootIn+1,inEnd);
    }
    return proot;
}

TreeNode* construct(int* pre,int* in,int len)
{
    if(pre==NULL || in==NULL || len<=0) return 0;
    return core(pre,pre+len-1,in,in+len-1);
}

void preOrder(TreeNode* root)
{
    if(root == NULL)
        return;
    printf("%d ",root->value);
    preOrder(root->pleft);
    preOrder(root->pright);
}

int main()
{
    int pre[] ={1,2,4,5,7,3,6};
    int in[] = {4,2,7,5,1,3,6};
    TreeNode* proot = construct(pre,in,sizeof(pre)/sizeof(int));
    preOrder(proot);
    int depth = treedepth(proot);
    printf("\ndepth:%d\n",depth);
    return 0;
}

题目2：平衡二叉树

输入一颗二叉树，判断该树是不是平衡二叉树。如果任意节点的左右子树的深度差不大于1,就是平衡的。

思路：
后续遍历二叉树，在遍历一个节点之前，我们已经遍历了它的左右子树。只要在遍历每个节点的时候，记录它的深度，我们就可以一边遍历一边判断每个节点是否平衡。

参考代码：

root@gt:/home/git/Keep-learning/myReading# ./a.out 
true=1,flase:0
1
root@gt:/home/git/Keep-learning/myReading# cat isbalanced.c 
#include <stdio.h>
#include <stdlib.h>
typedef struct treenode
{
    int value;
    struct treenode* pleft;
    struct treenode* pright;
}TreeNode;

int balancedCore(TreeNode* proot,int* pdepth)
{
    if(proot == NULL)
    {
        *pdepth = 0;
        return 1;
    }
    int left = 0;
    int right = 0;
    if(balancedCore(proot->pleft,&left) && balancedCore(proot->pright,&right))
    {
        int diff = left - right;
        if(diff <= 1 && diff >= -1)
        {
            *pdepth = 1 + (left > right?left:right);
            return 1;
        }
    }
    return 0;
}

int isbalanced(TreeNode* proot)
{
    int depth = 0;
    return balancedCore(proot,&depth);
}

TreeNode* core(int* preStart,int* preEnd,int* inStart,int* inEnd)
{
//前序遍历的地一个元素就是根节点
    int rootValue = preStart[0];
    TreeNode* proot = malloc(sizeof(TreeNode));
    proot->value = rootValue;
    proot->pleft = proot->pright = NULL;

//在中序遍历序号中找到根节点的值
    int* rootIn = inStart;
    while(rootIn <= inEnd && *rootIn != rootValue) ++rootIn;

    int leftLen = rootIn - inStart;
    int* leftPreEnd = preStart + leftLen;

    if(leftLen>0)
    {
        proot->pleft = core(preStart+1,leftPreEnd,inStart,inStart+leftLen-1);
    }
    if(leftLen < preEnd - preStart)
    {
        proot->pright = core(leftPreEnd+1,preEnd,rootIn+1,inEnd);
    }
    return proot;
}

TreeNode* construct(int* pre,int* in,int len)
{
    if(pre==NULL || in==NULL || len<=0) return 0;
    return core(pre,pre+len-1,in,in+len-1);
}

void preOrder(TreeNode* root)
{
    if(root == NULL)
        return;
    printf("%d ",root->value);
    preOrder(root->pleft);
    preOrder(root->pright);
}

int main()
{
    int pre[] = {1,2,4,5,7,3,6};
    int in[] = {4,2,7,5,1,3,6};
    TreeNode* proot = construct(pre,in,sizeof(pre)/sizeof(int));
    int balance = isbalanced(proot);
    printf("true=1,flase:0\n%d\n",balance);
    return 0;
}