【LeetCode】二叉树的深度 Java 题解

关注

发布于: 5 小时前

题目描述

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

例如：
给定二叉树 [3,9,20,null,null,15,7]，
    3   / \  9  20    /  \   15   7返回它的最大深度 3 。
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的每日一题是求二叉树深度，求二叉树的深度，需要遍历整个树所有的节点。常见的遍历树所有节点的方法有 DFS，BFS。
DFS 全称是 Depth First Search，中文名是深度优先搜索，是一种用于遍历或搜索树或图的算法。所谓深度优先，就是说每次都尝试向更深的节点走。我们一般使用递归到方式实现 DFS 算法。
BFS 全称是 Breadth First Search，中文名是宽度优先搜索，也叫广度优先搜索。我们一般使用队列俩实现 BFS 算法。
具体到这个题目，DFS 方法采用自底向上的思路遍历，分别求出左子树和右子树的最大深度，并求出最大值。
BFS 方法采用自顶向下的思路遍历，根节点的高度是 1，高度逐层递增，容易理解。

通过代码

DFS 解法

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    public int maxDepth(TreeNode root) {        if (root == null) {            return 0;        }
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));    }}

复制代码

BFS 解法

    public int maxDepth(TreeNode root) {        if (root == null) {            return 0;        }        Queue<TreeNode> queue = new LinkedList<>();        queue.add(root);        int ans = 0;        while (!queue.isEmpty()) {            ans++;            int size = queue.size();            for (int i = 0; i < size; i++) {                TreeNode temp = queue.poll();                if (temp.left != null) {                    queue.add(temp.left);                }                if (temp.right != null) {                    queue.add(temp.right);                }            }        }
        return ans;    }

复制代码

总结

DFS 解法的时间复杂度是 O(n) , 空间复杂度是 O(n)
BFS 解法的时间复杂度是 O(n) , 空间复杂度是 O(n)
二叉树是最常见到考察题目，常见问题我们一定要多练习，熟练掌握，才能胸有成竹。
坚持算法每日一题，加油！

发布于: 5 小时前阅读数: 2

原文链接:【http://xie.infoq.cn/article/0f34e38370df575de4c90dd58】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】二叉树的深度 Java 题解

题目描述

思路分析

通过代码

总结

HQ数字卡

评论