题目描述

给定一个二叉树,找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例:
给定二叉树 [3,9,20,null,null,15,7],

     3
    / \
   9  20
     /  \
    15   7
 返回它的最大深度 3 。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximum-depth-of-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解法1 – DFS

这是道经典的BinaryTree的模版题,我们声明函数private int helper(TreeNode node, int depth) ,当node是叶子结点时返回depth,如果node的左子树非空则递归调用helper(node.left, depth+1);当node的右子树非空,则递归调用helper(node.right, depth+1); 当node为空,则返回0。

时间复杂度O(n),空间复杂度O(n)。全部代码如下:

class Solution {
    public int maxDepth(TreeNode root) {
        return helper(root, 1);
    }

    private int helper(TreeNode node, int depth) {
        if (node == null)
            return 0;
        
        if (node.left == null && node.right == null)
            return depth;

        int maxDepth = helper(node.left, depth + 1);

        maxDepth = Math.max(maxDepth, helper(node.right, depth + 1));

        return maxDepth;
    }
}

解法2 – BFS

当然这道题也可以用BFS来做,我们需要一个队列,还有一个Map<TreeNode, Integer>用来存放节点对应的深度。如果node的左子树非空,就将它如队列,然后depth+1放入map中;右子树同理。然后还需要一个存放答案的变量ans,如果取出节点的深度大于ans就更新它,最后返回ans。

复杂度和解法1相同,但因为用到了Map导致overhead比较大,实际运行时间比解法1慢很多。全部代码如下:

class Solution {
    public int maxDepth(TreeNode root) {
        int ans = 0;
        if (root == null)
            return ans;

        Queue<TreeNode> queue = new LinkedList<>();
        Map<TreeNode, Integer> nodeDepth = new HashMap<>();

        queue.offer(root);
        nodeDepth.put(root, 1);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            int depth = nodeDepth.get(node);

            ans = Math.max(ans, depth);

            if (node.right != null) {
                queue.offer(node.right);
                nodeDepth.put(node.right, depth + 1);
            }

            if (node.left != null) {
                queue.offer(node.left);
                nodeDepth.put(node.left, depth + 1);
            }
        }

        return ans;
    }
}
pwrliang Algorithms, BFS, DFS, Tree, Uncategorized , ,

Leave a Reply

Your email address will not be published. Required fields are marked *