题目：
输入一颗二叉树的根节点，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
struct BinaryTreeNode {
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};
解法：
int treeDepth(BinaryTreeNode* pRoot) {
if (pRoot == 0) return 0;
int left = treeDepth(pRoot->m_pLeft);
int right = treeDepth(pRoot->m_pRight);
return 1+ (left > right ? left : right);
}
拓展
判断一颗二叉树是否是一颗平衡二叉树。平衡二叉树，对任何一个结点，左右子树的深度差距不超过1.
解法一：
从根节点开始，对每一个结点判断左右子树是否平衡。判断的方法：求左右子树的深度，如果深度相差不超过1，即可判断为平衡二叉树
bool isBalanced(BinaryTreeNode* pRoot) {
if (pRoot == 0) return true;
int left = treeDepth(pRoot->m_pLeft);
int right = treeDepth(pRoot->m_pRight);
int diff = left - right;
if (!(diff <= 1 && diff >= -1)) {
return false;
}
return isBalanced(pRoot->m_pLeft) && isBalanced(pRoot->m_pRight);
}
该方法，会重复遍历结点
解法二：
bool isBalanced(BinaryTreeNode* pRoot, int *depth) {
if (pRoot == 0) {
*depth = 0;
return true;
}
int left = 0;
int right = 0;
bool leftBalanced = isBalanced(pRoot->m_pLeft, &left);
bool rightBalanced = isBalanced(pRoot->m_pRight, &right);
int diff = left - right;
if (leftBalanced && rightBalanced && (diff <= 1 && diff >= -1)) {
*depth = 1 + (left > right ? left : right);
return true;
}
return false;
}
