首先，我们先把二叉树的前中后遍历用递归写一遍：
先定义二叉树数据结构：
Public classTreeNode {
public intvalue;
publicTreeNodeleft;
publicTreeNoderight;
}
前序遍历：
public voidforeSearch(TreeNode treeNode) {
if(treeNode ==null) {
return;
}
System.out.print(treeNode.value);
foreSearch(treeNode.left);
foreSearch(treeNode.right);
}
中序遍历：
public voidmiddleSearch(TreeNode treeNode) {
if(treeNode ==null) {
return;
}
middleSearch(treeNode.left);
System.out.print(treeNode.value);
middleSearch(treeNode.right);
}
后序遍历：
public voidbackSearch(TreeNode treeNode) {
if(treeNode ==null) {
return;
}
backSearch(treeNode.left);
backSearch(treeNode.right);
System.out.print(treeNode.value);
}
是不是简单到爆？可是在第一次写这个递归的时候总是没有把握，并且时常写递归写完后就算是对的也不知道自己为什么这么写，在我看来递归本来就算是很难理解得一个东西了，能把递归理解得很好很不错啦（也可能是我自己太笨）。
那我们来一步一步分析怎么写的这个前序遍历，首先，我们要确定这个遍历它的规律，因为递归你一定是每次执行都符合同一个规律，这样才能使用同样的代码嘛。
分析它的数据结构了，三部分：当前节点，左子树，右子树，对不对，每个子树又包含这三个部分 ，以此重复，什么时候完呢？就是当子树不存在了，说明这个树到底了，对不对。
那么前序遍历规律出来了，先根节点，然后左节点，然后右节点，遍历结果为：
临界条件为：子树为空。
那么我们就写个方法，遍历树的，foreSearch()，递归很重要的地方在于，找到跳出递归的条件，这里的条件是子树为空，遍历的关键代码：
首先遍历根嘛，我们这里就打印根节点：System.out.print(treeNode.value);
打印完根节点后，我们要遍历左边的节点，又由于左边的节点可能是一个子树，对吧，对于子树的遍历我们仍然是先根节点再左再右，跟我们定义的foreSearch方法一样的，那么我们便调用自己：foreSearch(treeNode.left);它会遍历左子树，然后需要继续遍历右子树：
foreSearch(treeNode.right);最后定义跳出递归的条件：
if(treeNode ==null) {
return;
}
好，再换个场景，求二叉树的最大深度，首先，我们要分析一棵二叉树的最大深度等于什么？ 是不是得考虑到底是左子树更深还是右子树更深？ 那我们是不是就要求左子树的深度和右子树的深度？然后再得到最大那个深度加上1就是该子树的最大深度了？
好的我们知道了这里能够重复的方法就是求树的深度的方法，因为求当前节点的最大深度和求左子树的最大深度的方法是一样的，那么我们来定义一个求树深度的方法：
public intgetMostDeepth(TreeNode treeNode) {
}
然后我们是不是求左子树的深度？intleftDeep = getMostDeepth(treeNode.left);
然后求右子树的深度：intrightDeep = getDepth(treeNode.right);
最后树的长度为左右子树长度更长的那个值加1：returnleftDeep > rightDeep ? leftDeep +1: rightDeep +1;
OK方法已经组合好了：
public intgetMostDeepth(TreeNode treeNode) {
intleftDeep = getMostDeepth(treeNode.left);
intrightDeep = getDepth(treeNode.right);
returnleftDeep > rightDeep ? leftDeep +1: rightDeep +1;
}
现在还缺什么呢，就是跳出递归的条件，大家想想到什么情况下就不再继续了，那就是子树为空了嘛，已经到叶节点了是不是就不再往下了嘛，那么跳出条件仍然是treeNode ==null，当节点为空时，说明了什么，说明该节点的深度为0，那么我们就返回0就是了：
public intgetMostDeepth(TreeNode treeNode) {
if(treeNode ==null) {
return0;
}
intleftDeep = getMostDeepth(treeNode.left);
intrightDeep = getDepth(treeNode.right);
returnleftDeep > rightDeep ? leftDeep +1: rightDeep +1;
}
完整方法就出来了，是不是很容易？
这里总结几点就是：
1.总结规律，你知道你是在写一个递归方法，那么就得定义出这个递归方法是干什么的。
2.调用自己
3.跳出条件，跳出时的判断条件是什么以及当前条件下该返回什么。
需要注意的是，如果你的跳出条件有问题的话，递归很容易产生stackoverflow。
好吧，可能写完还是没什么帮助，就当我自己给自己记录下，因为递归确实很难理解。
网友评论