二叉树相关题目
//判定二叉樹是不是平衡二叉樹
//網(wǎng)上的版本要不斷的重復(fù)計算
//返回-1，以x為頭的子樹不是平衡二叉樹
//否則返回值是 子樹的深度
int BalantTree(Node *x)
{if(x ==NULL)return 0;int right = BalantTree(x.right);int left = BalantTree(x.left);if(right<0 || left<0)return -1;if(abs(right - left)>1)return -1;return 1+((right>left)?right:left);
}
template<typename?T>?? int?DepthTree(BSTreeNode<T>?*pbs)?? {?? ????if?(pbs==NULL)?? ????????return?0;?? ????else?? ????{?? ????????int?leftLength=DepthTree(pbs->left);?? ????????int?rigthLength=DepthTree(pbs->right);?? ????????return?1+(leftLength>rigthLength???leftLength:rigthLength);?? ????}?? }?? ?? template<typename?T>?? bool?isBalanceTree(BSTreeNode<T>?*pbs)?? {?? ????if?(pbs==NULL)?? ????{?? ????????return?true;?? ????}?? ?? ????int?depthLeft=DepthTree(pbs->left);?? ????int?depthRight=DepthTree(pbs->right);?? ?? ????if?(abs(depthLeft-depthRight)>1)??? ????????return?false;?? ????else?? ????????return?isBalanceTree(pbs->left)?&&?isBalanceTree(pbs->right);?? } ?
網(wǎng)上的版本
總結(jié)
- 上一篇： 操作系统相关题目
- 下一篇： 二叉树两个节点的公共节点