输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

//方案一：

public class Solution {

int max=0;

int temp=0;

public int TreeDepth(TreeNode root) {

   f(root);
    return max;
}

public void f(TreeNode root){

    if(root==null){
        if(temp>max)
            max=temp;
        return;
    }
   
    temp++;
    f(root.left);
    f(root.right);
     temp--;
    
    
}

}

//方案二：

public class Solution {

public int TreeDepth(TreeNode root) {

  if(root==null)
  
      return 0;
	  
    return (1+TreeDepth(root.left))>(1+TreeDepth(root.right))?(1+TreeDepth(root.left)):(1+TreeDepth(root.right));
}

}

//方案三 层序遍历非递归

import java.util.*;

public class Solution {

public int TreeDepth(TreeNode root) {

  int count=0;
  int curCount=1;
  int nextCount=0;
  int totalCount=0;
  
  if(root==null)
      return totalCount;
    
  Queue<TreeNode> queue = new LinkedList<TreeNode>();
    
  queue.add(root);
    
  while(!queue.isEmpty()){
      
      TreeNode temp=queue.remove();
      count++;
      
      if(temp.left!=null){
         nextCount++;
          queue.add(temp.left);
      }
      if(temp.right!=null){
          nextCount++;
          queue.add(temp.right);
      }
      
       if(count==curCount){
          totalCount++;
          count=0;
          curCount=nextCount;
           nextCount=0;
      }
      
      
  }

    return totalCount;
}

}

//方案四：类似先序遍历，实际上线找右子树的最大高度，再找左子树的最大高度

//也可以先左子树进栈，然后右子树进栈，也就是先找左子树的最大高度，再找右子树的最大高度

import java.util.*;

public class Solution {

public int TreeDepth(TreeNode root) {

  int max=0;
  if(root==null)
      return max;
    
   Stack<TreeNode> stack1=new Stack<TreeNode>();
    stack1.push(root);
   Stack<Integer> stack2=new Stack<Integer>();
    stack2.push(0);
    
    while(!stack1.isEmpty()){
        
        TreeNode temp = stack1.pop();
        
        int num=stack2.pop();
        num++;
        
        if(num>max)
            max=num;
        
        if(temp.left!=null){
            stack1.push(temp.left);
            stack2.push(num);
        }
        
        if(temp.right!=null){
            stack1.push(temp.right);
            stack2.push(num);
        }
        
    }

    return max;
}

}