LeetCode-104-二叉树的最大深度

104. 二叉树的最大深度

难度简单893收藏分享切换为英文接收动态反馈

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

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

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

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

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。

解题思路

DFS
找出终止条件：当前节点为空
找出返回值：节点为空时说明高度为 0，所以返回 0；节点不为空时则分别求左右子树的高度的最大值，同时加1表示当前节点的高度，返回该数值
某层的执行过程：在返回值部分基本已经描述清楚
时间复杂度：O(n)

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

        int left = maxDepth(root.left);
        int right = maxDepth(root.right);

        return left>right ? left+1:right+1;
    }
}

image-20210607091507462

BFS:

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int level=0;
        LinkedList<TreeNode> deque = new LinkedList<>();
        deque.add(root);
        int size = 0;
        while(!deque.isEmpty()) {
            size = deque.size();
            level++;
            for(int i = 0 ; i< size;i++) {
                TreeNode cur = deque.pollLast();
                if(cur.left != null) {
                    deque.addFirst(cur.left);
                }
                if(cur.right != null) {
                    deque.addFirst(cur.right);
                }
            }
        }
        return level;
    }
}

image-20210607091420083