二叉樹的深度

來自專欄 ath0的演算法小屋

二叉樹的深度

輸入一顆二叉樹的根節點，求該樹的深度。從根節點到葉子節點依次經過的節點形成樹的一條路徑，最長路徑的長度為樹的深度。

思路：樹的高度為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("
depth:%d
",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
%d
",balance); return 0;}

推薦閱讀：