题目：输入一棵二叉树的根节点，求该数的深度。
从根节点到叶结点依次进过的结点（含根，叶结点）形成树的一条路径，最长路径的长度为树的深度。
比如。例如以下图的二叉树的深度为４。由于它从根节点到叶结点的最长的路径包括４个结点（从根结点１開始，经过２和结点５，终于到达叶结点７）
watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="">
我们能够从还有一种角度来理解树的深度。
假设一棵树仅仅有一个结点，它的深度为1，假设根节点仅仅有左子树而没有右子树，那么树的深度应该是其左子树的深度+1.相同假设根节点仅仅有右子树而没有左子树，那么树的深度应该是其右子树+1.假设既有左子树又有右子树。那概述的深度就是左、右子树的深度的较大值加1.。
利用这个思路，我们能够用递归来实现代码：
//普通二叉树求深度
public int treeDepth(BinaryTreeNode root){
if(root == null)
return 0;
int nLeft = treeDepth(root.leftNode);
int nRight = treeDepth(root.rightNode);
return (nLeft > nRight)? (nLeft+1):(nRight+1);
}
假设公司对编程能力有较高的要求。面试官可能会追加一个与前面的问题相关但难度较大的问题，比方，应聘者做完上面的问题后，面试官追问：
题目二：输入一棵二叉树的根节点。推断该树是不是平衡的二叉树。假设某二叉树中随意结点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
须要反复遍历结点多次的解法，简单但不足以打动面试官
有了求二叉树的深度的经验之后再解决问题，我们非常easy就能想到一个思路：在遍历树的每一个结点的时候，调用函数TreeDepth得到它的左右子树的深度。假设每一个结点的左右子树的深度相差不超过1，依照定义它就是一棵平衡的二叉树。
这样的思路实现的代码例如以下：
//推断是否是一颗平衡二叉树
public boolean isBalanced(BinaryTreeNode root){
if(root ==null)
return true;
int left = treeDepth(root.leftNode);
int right = treeDepth(root.rightNode);
int diff = left - right;
if(diff > 1 || diff <-1)
return false;
return isBalanced(root.leftNode) && isBalanced(root.rightNode);
}
上面的代码固然简洁，但我们也注意到因为一个结点会被反复遍历多次，这样的思路的时间效率不高。
比如在函数isBalanced中输入上图中的二叉树，我们将首先推断根节点是不是平衡的。
此时我们网函数TreeDepth输入左子树的根节点时须要遍历结点4，5。7.接下来推断以结点2为根节点的子树是不是平衡树的时候。仍然会遍历结点4，5，7.毫无疑问，反复遍历同一个结点会影响性能。接下来我们寻找不须要反复遍历的算法。
每一个结点仅仅遍历一次的解法，正是面试官喜欢的算法
假设我们用后序遍历的方式遍历二叉树的每一个结点。在遍历一个结点之前我们就已经遍历了它的左右子树。仅仅要在遍历每一个结点的时候我们记录它的深度（某一节点的深度等于它到叶结点的路径的长度），我们就能够一边遍历一边推断每一个结点是不是平衡二叉树。
以下是这样的思路的实现代码：
//高效率的推断是否是一棵平衡二叉树
public boolean isBalanced2(BinaryTreeNode root){
int depth = 0;
return isBalanced2(root,depth);
}
public boolean isBalanced2(BinaryTreeNode root,int depth){
if(root == null){
depth = 0;
return true;
}
int left = 0,right = 0;
if(isBalanced2(root.leftNode,left) && isBalanced2(root.rightNode,right)){
int diff = left-right;
if(diff <= 1 && diff >= -1){
depth = 1+(left > right?left : right);
return true;
}
}
return false;
}
在上面的代码中，我们用后序遍历的方式遍历整棵二叉树。在遍历某结点的左右子树结点之后，我们就能够依据它的左右子树的深度推断它时不时平衡的，并得到当前结点的深度。当最后遍历到树的根节点的时候，也就推断了整棵二叉树是不是平衡二叉树。