剑指offer——二叉树的深度与平衡二叉树的判断

通过后续遍历，可以减少重复访问

#include <iostream>
#include <string>
using namespace std;

struct BinaryTreeNode
{
 int m_data;
 BinaryTreeNode* m_left;
 BinaryTreeNode* m_right;
};

int TreeDepth(BinaryTreeNode* pRoot)
{
 if (pRoot==NULL)
 {
  return 0;
 }
 int nleft=TreeDepth(pRoot->m_left);
 int nright=TreeDepth(pRoot->m_right);
 return (nleft>nright)?(nleft+1):(nright+1);
}

bool IsBalance(BinaryTreeNode* pRoot,int *pDepth)
{
 if (pRoot==NULL)
 {
  *pDepth=0;
  return true;
 }
 int left,right;
 if(IsBalance(pRoot->m_left,&left)&&IsBalance(pRoot->m_right),&right)
 {
  int diff=left-right;
  if (diff<=1&&diff>=-1)
  {
   *pDepth=1+(left>right)?left:right;
   return true;
  }
 }
 return false;
}