剑指Offer-二叉树的深度

二叉树的深度

题目

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

思路

DFS
层次遍历

代码

import java.util.LinkedList;
import java.util.Queue;

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

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

        }

    }

    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;
    }

    public int TreeDepth_II(TreeNode root){
        int depth = 0;
        if (root==null){
            return 0;
        }

        Queue<TreeNode> quene = new LinkedList<>();
        quene.add(root);

        int count = 0,nextCount = 1;
        while (quene.size()!=0){
            TreeNode top = quene.poll();
            count++;
            if (top.left!=null){
                quene.add(top.left);
            }

            if (top.right!=null){
                quene.add(top.right);
            }

            if (count==nextCount){
                nextCount = quene.size();
                count = 0;
                depth++;
            }
        }
        return depth;
    }
}