二叉树最大深度递归版与非递归版算法实现

1.递归的本质是通过栈来保存状态，然后再次调用自己进入新的状态，函数返回的时候回到上次保存的状态。

所以递归转化为非递归，一般通用方法是通过栈保存当前结果状态。

2.举个例子：

二叉树最大深度（递归版）

 1 public static int deep(Tree tree){
 3      if(tree == null){
 5        return 0；
 7     }
 8 
 9   if(tree.getLeft() == null && tree.getRight() == null){
11     return 1;
13   }  
14 
15    int ltree = deep(tree.getLeft());//遍历左子树深度
17    int rtree = deep(tree.getRight());//遍历有子树深度
18 
19    return ltree > rtree ? ltree+1:rtree+1;//比较左右子树深度，返回打的一边
20 
21 }

二叉树最大深度（非递归版）

 1     public static int deep2(Tree tree){
 2               if(tree == null){
 3                      return 0;
 4               }
 5               int max = 0;
 6               Stack<Tree> stacks = new Stack<Tree>();//节点栈
 7               Stack<Integer> heights = new Stack<Integer>();//保存当前节点深度状态
 8               heights.push(1);
 9               stacks.push(tree);
10               while (!stacks.isEmpty()) {
11                       Tree curTree = stacks.pop();
12                       int height = heights.pop();
13                      
14                       if(curTree.getLeft() != null){
15                             heights.push(height+1);//记录节点深度值
16                             stacks.push(curTree.getLeft());
17                       }
18                      
19                       if(curTree.getRight() != null){
20                             heights.push(height+1);//记录节点深度值
21                             stacks.push(curTree.getRight());
22                       }
23                       if(max < height){
24                             max = height;
25                       }
26               }
29               return max;
30        }

3.总结.

递归容易造成栈溢出，通过非递归版实现，更节省空间。

递归算法简单，一般很难理解，非递归版代码量多，但易理解。面试时要你写个递归版的实现，不妨可以试试非递归版实现。