来自剑指offer
求树的深度
用递归做很简单，，只要知道递归出口语句的别写错。
struct BinaryTreeNode{int m_Value;BinaryTreeNode* m_pLeft;BinaryTreeNode* m_pRight;};int TreeDepth(BinaryTreeNode* pRoot){if (pRoot == NULL)return 0;int nLeftDepth = TreeDepth(pRoot->m_pLeft);int nRightDepth = TreeDepth(pRoot->m_pRight);return (nLeftDepth>nRightDepth)?(nLeftDepth+1):(nRightDepth+1);}判断该树是否为平衡二叉树
方法一：调用上述函数求每个节点的左右孩子深度
bool IsBalanced(BinaryTreeNode* pRoot){if(pRoot== NULL)return true;int nLeftDepth = TreeDepth(pRoot->m_pLeft);int nRightDepth = TreeDepth(pRoot->m_pRight);int diff = nRightDepth-nLeftDepth;if (diff>1 || diff<-1)return false;return IsBalanced(pRoot->m_pLeft)&&IsBalanced(pRoot->m_pRight);}方法二：由于上述方法在求该结点的的左右子树深度时遍历一遍树，再次判断子树的平衡性时又遍历一遍树结构，造成遍历多次。因此方法二是一边遍历树一边判断每个结点是否具有平衡性。bool IsBalanced(BinaryTreeNode* pRoot, int* depth){if(pRoot== NULL){*depth = 0;return true;}int nLeftDepth,nRightDepth;bool bLeft= IsBalanced(pRoot->m_pLeft, &nLeftDepth);bool bRight = IsBalanced(pRoot->m_pRight, &nRightDepth);if (bLeft && bRight){int diff = nRightDepth-nLeftDepth;if (diff<=1 || diff>=-1){*depth = 1+(nLeftDepth > nRightDepth ? nLeftDepth : nRightDepth);return true;}}return false;}bool IsBalanced(BinaryTreeNode* pRoot){int depth = 0;return IsBalanced(pRoot, &depth);}
人生并不在于获取，更在于放得下。放下一粒种子，收获一棵大树；
