二叉树的深度（前序遍历）

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

import java.util.LinkedList;
import java.util.List;
import java.util.Collections;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
//自己写的递归
public class Solution {
   
	int index =0;
	List<Integer> list = new LinkedList<Integer>(); 
public List<Integer> TreeDepth1(TreeNode root) {
	if(root==null){
		list.add(index);	
		return list;
	}
	++index;
	TreeDepth1(root.right);
	
	TreeDepth1(root.left);
	--index;
	
	return list;
}
   public int TreeDepth(TreeNode root) {
	   if(root ==null){
		   return 0;
	   }
	   TreeDepth1(root);
	   Collections.sort(list);
	return list.get(list.size()-1);
}
//别人写的递归
 public int TreeDepth(TreeNode pRoot)
    {
        if(pRoot == null){
            return 0;
        }
        int left = TreeDepth(pRoot.left);
        int right = TreeDepth(pRoot.right);
        return Math.max(left, right) + 1;
    }
    //非递归
     public int TreeDepth(TreeNode root) {
		 if(root==null){
			return 0;
		 }
		 Queue<TreeNode> qt = new LinkedList<>(); 
		 qt.offer(root);
		 int index=0;
		 int left =0;
		 int right =1;
		 while(qt.size()>0){
			 ++left;
			 TreeNode t= qt.poll();
			 if(t.left!=null){
				 qt.offer(t.left);
			 }
			 if(t.right!=null){
				 qt.offer(t.right);
			 }
			 if(left==right){
				 right =qt.size();
				 left =0;
				 ++index;
			 }
			 
		 }
		 
		return index;
	    
	}
}

总结一下：（非递归）当遍历二叉树是一层一层的遍历时用队列，还有那种直接根节点到叶子节点，不用考虑同一个父节点的另一个子节点，可以当成前序遍历。
如果是中序遍历那就要考虑父节点另一个子节点，三个成一个模型，递归到根节点，但是有个叶子节点要和根节点相邻，所以需要额外的自己定义的一个节点记录下来