二叉树的深度

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

方法一、递归

实际上考察  树的三种遍历形式 （递归） 三种都可以 

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
*/
public class Solution {
    public int TreeDepth(TreeNode root) {
        if(root==null)//根节点为空
            return 0;
          if(root.left==null&&root.right==null)    //只有根节点
            return 1;
          int left = TreeDepth(root.left);//左序遍历
          int right= TreeDepth(root.right);//右序遍历
        return left>right? left+1:right+1;
        
    }
   
}

 方法二：非递归写法：层次遍历

1）当node=10,第一次循环示例

TreeNode top = queue.poll();//获取队列头部的元素，并删除该元素，   top=10
                                       // 如果此队列为空，则返回null。
            count++;                                                                                      count=1;
            if(top.left != null){
                queue.add(top.left);                                                                queue={node6}
            }
            if(top.right != null){
                queue.add(top.right);                                                               queue={node6,node14}  
            }
            if(count == nextCount){
                nextCount = queue.size();                                                             nextcount==2;
                count = 0;                                                                                       count=0;
                depth++;                                                                                        depth=1;
            }

代码及测例： 

package pag1;
import java.util.LinkedList;
import java.util.Queue;

public class SolutionListNode {
    public int TreeDepth(TreeNode pRoot)
    {
        if(pRoot == null){
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(pRoot);
        int depth = 0, count = 0, nextCount = 1;
        while(queue.size()!=0){
            TreeNode top = queue.poll();
            count++;
            if(top.left != null){
                queue.add(top.left);
            }
            if(top.right != null){
                queue.add(top.right);
            }
            if(count == nextCount){
                nextCount = queue.size();
                count = 0;
                depth++;
            }
        }
        return depth;
    }
        int GetLastIndex(int[]data,int k,int start,int end){
            if(start > end)
                return -1;
            int mid = start+(end-start)/2;
            if(data[mid] == k){
                if((mid <end && data[mid+1] != k) || mid == end)
                    return mid;
                else
                    start = mid+1;
            }else{
                if(data[mid] > k)
                    end = mid - 1;
                else
                    start = mid + 1;
            }
            return GetLastIndex(data,k,start,end);
    }
    public static void main(String[] args) {
        TreeNode root = new TreeNode(10);
        TreeNode six = new TreeNode(6);
        TreeNode four = new TreeNode(4);
        TreeNode eight = new TreeNode(8);
        TreeNode fourteen = new TreeNode(14);
        TreeNode twelve = new TreeNode(12);
        TreeNode sixteen = new TreeNode(16);

        root.left = six;
        root.right = fourteen;

        six.left = four;
        six.right = eight;

        four.left = null;
        four.right = null;

        eight.left = null;
        eight.right = null;

        fourteen.left = twelve;
        fourteen.right = sixteen;

        twelve.left = null;
        twelve.right = null;

        sixteen.left = null;
        sixteen.right = null;


        SolutionListNode test=new SolutionListNode();
        System.out.println(test.TreeDepth(root));
    }
}