二叉树的深度

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

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

参考代码：

root@gt:/home/git/Code# ./a.out 1 2 4 5 7 3 6 depth:4root@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:01root@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;}