频道栏目
首页 > 考试 > 其他 > 正文
leetcode104~二叉树的最大深度添加到列表
2017-02-27 12:12:00         来源:stone  
收藏   我要投稿

leetcode104~二叉树的最大深度添加到列表。

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

求解二叉树的深度,该题比较简单~~~

两种解法,递归和非递归

非递归使用层序遍历,思想:curnum记录当前层节点个数, nextnum记录下一层节点个数 ,遍历完一层depth++,层序遍历肯定是遍历到最底层。

public class MaximumDepthofBT {
    public int maxDepth2(TreeNode root) {
        if(root==null) return 0;
        int leftdepth = maxDepth(root.left);
        int rightdepth = maxDepth(root.right);
        return Math.max(leftdepth, rightdepth)+1;
    }

    //层序遍历
    //思想:curnum记录当前层节点个数, nextnum记录下一层节点个数 ,遍历完一层depth++,层序遍历肯定是遍历到最底层 
    public int maxDepth(TreeNode root) {
        if(root==null) return 0;
        Queue queue = new LinkedList<>();
        queue.offer(root);
        int curnum = 1;
        int nextnum = 0;
        //记录深度
        int depth = 0;
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            curnum--;
            if(node.left!=null) {
                queue.offer(node.left);
                nextnum++;
            }
            if(node.right!=null) {
                queue.offer(node.right);
                nextnum++;
            }
            if(curnum==0) {
                curnum=nextnum;
                nextnum=0;
                depth++;
            }
        }
        return depth;
    }
}

 

点击复制链接 与好友分享!回本站首页
上一篇:给定一个字符串S,在S中找到最长的回文子串
下一篇:leetcode112~路径总和添加到列表
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站