面试题39：二叉树的深度
题目一：输入一颗二叉树的根节点，求该树的深度。从根节点到叶节点一次经过的节点形成树的一条路径，最长路径的长度为树的深度。
二叉树节点定义如下：
```struct BinaryTreeNode { int value; BinaryTreeNode* left; BinaryTreeNode* right; BinaryTreeNode(int data=int()) :value(data),left(NULL),right(NULL) {} }
* * *
### 分析
此题可利用递归很方便的完成，步骤如下：
* 判断参数root是否为空？为空就返回0；
* 否则计算root的左右子树的高度；
* 比较左右子树高度，取较大者，返回较大的值加1（root自身占一层）。
代码如下：
```int Depth(BinaryTreeNode* root)
{
if(root==NULL)
return 0;
int LeftDepth=Depth(root->left);
int RightDepth=Depth(root->right);
return LeftDepth>RightDepth?LeftDepth+1:RightDepth+1;
}
题目二：输入一颗二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意两个节点的左右子树的深度相差不超过1，那么它就是一颗平衡二叉树。
分析
最容易想到的就是遍历二叉树，每遍历到一个节点时，去求它的左右子树的深度并比较即可。然而这种方法需要将很多节点遍历多次。如下图：
求1的深度时，需要遍历剩下的所有节点。然后求2的深度时，需要遍历4和7两个节点。求3的深度时，又需要遍历5,6,8三个节点。这样导致时间复杂度较高。
有没有办法减少遍历节点的次数呢？答案是有的。那就是将每次遍历过的节点保存起来。我们可以将从根节点到叶节点所经过的所有节点看成一条路径。每次向下进入子树时，将当前节点保存进路径里面。从子树退回到父节点时，再将它从路径中删除。如此，我们便可以只遍历一次。求遍历过程中路径的最大值就可以，即最长路径。
代码如下：
```bool IsBalanced(BinaryTreeNode* root,int& depth) { if(root==NULL) { depth=0; return true; } int left,right; if(IsBalaced(root->left,left) && _IsBalanced(root->right,right) { int diff=right-left; if(diff>=-1 && diff <=1) { depth=left>right?left+1:right+1; return true; } } return false; }
bool IsBalanced(BinaryTreeNode* root) { int depth=0; return _IsBalanced(root,depth); } ```
以上
如果你有任何想法或是可以改进的地方，欢迎和我交流！
完整代码及测试用例在github上：点我前往(题目一) 点我前往(题目二)