104. 二叉树的最大深度

- 日理万妓 2023-02-18 01:52 23阅读 0赞

# 题目来源 #

[面试题55 - I. 二叉树的深度][55 - I.]  
[104. 二叉树的最大深度][104.]

# 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]

# 题目解析 #

## 后续遍历 ##

此树的深度 等于 左子树的深度 与 右子树的深度 中的 最大值 +1。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][20200615104822725.png]

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

![在这里插入图片描述][20200615171843100.png]

## 层次遍历 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 2]

public int maxDepth(TreeNode root) {
        
            if(root == null){
        
                return 0;
            }
    
            LinkedList<TreeNode> queue = new LinkedList<>(), tmp;
            queue.offer(root);
            int ans = 0;
            while (!queue.isEmpty()){
        
                tmp = new LinkedList<>();
                for (TreeNode node: queue) {
        
                    if (node.left != null){
        
                        tmp.offer(node.left);
                    }
                    if (node.right != null){
        
                        tmp.offer(node.right);
                    }
                }
                queue = tmp;
                ans++;
            }
    
            return ans;
        }

![在这里插入图片描述][20200615110956998.png]

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

![在这里插入图片描述][20200615111309579.png]

[55 - I.]: https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/
[104.]: https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200615110647348.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2020061510472193.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[20200615104822725.png]: https://img-blog.csdnimg.cn/20200615104822725.png
[20200615171843100.png]: https://img-blog.csdnimg.cn/20200615171843100.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200615110601863.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[20200615110956998.png]: https://img-blog.csdnimg.cn/20200615110956998.png
[20200615111309579.png]: https://img-blog.csdnimg.cn/20200615111309579.png