算法通关村——轻松搞定最大深度问题

迈不过友情╰ 2024-03-23 20:39 91阅读 0赞

## 前言 ##

> 二叉树的深度：从根节点到当前节点的最长简单路径边的条数

### 题目 ###

> 给定一个二叉树，找出其最大深度，二叉树的深度为根节点到最远叶子节点的最长路径上的节点数

#### 说明 ####

> 如下图所示，对于node(3) ， 最大深度自然是左右子节点+1，左右子节点有的可能为空，只要有一个，树的最大高度就是1+1=2.
> 
> 对于node（20），最大深度自然是左右子节点+1，左右子节点有的可能为空，只要有一个，树的最大高度就是1+1=2.用代码表示就是
> 
> int depth = 1 + max(leftDepth,rightDepth);
> 
> 而对于3，则是左右子树深度最大的那个然后再+1，具体谁更大，则不必关心。所以对于node(3)的判断逻辑就是：
> 
> int leftDepth = getDepth(root.left); // 左
> 
> int rightDepth = getDepth(root.right); // 右
> 
> int depth = 1 + max(leftDepth,rightDepth); // 中

![image.png][]

> 当root == null的时候返回0

#### 二叉树的最大深度问题 ####

##### 代码实现 #####

public int getDepth(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftDepth = getDepth(root.left);
        int rightDepth = getDepth(root.right);
        return Math.max(leftDepth,rightDepth)+1;
        
    }

#### N叉树的最大深度问题 ####

##### 代码实现 #####

> N叉树的定义

class MutilTreeNode {
        public int data ;
        public List<MutilTreeNode> children;
    
        public MutilTreeNode() {
        }
    
        public MutilTreeNode(int data) {
            this.data = data;
        }
    
        public MutilTreeNode(int data, List<MutilTreeNode> children) {
            this.data = data;
            this.children = children;
        }
    }

> 方法实现

public int maxDepth(MutilTreeNode root){
        if(root == null){
            return 0;
        }
        if(root.children.isEmpty){
            return 1;
        }else{
            List<Integer> height = new ArrayList<>();
            for(MutilTreeNode child : root.children){
                height.add(maxDepth(child));
            }
            return Collections.max(height);
        }
    }

[image.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/a72c8c2f993a472e859192d6d362a9bb.png