（二叉树）原来Java 求解二叉树的最大深度如此简单！！！

深碍√TFBOYSˉ_ 2023-01-20 13:48 29阅读 0赞

### 文章目录 ###

*   *  一、求解二叉树的最大深度
     *   *  1. 题目
         *  2. 递归法
         *  3. 迭代法
     *  二、求解N叉树的最大深度
     *   *  1. 题目
         *  2. 递归法
         *  3. 迭代法
     *  三、总结

## 一、求解二叉树的最大深度 ##

### 1. 题目 ###

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

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

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

示例：  
给定二叉树 \[3,9,20,null,null,15,7\]，  
![在这里插入图片描述][20210513103828721.png]

### 2. 递归法 ###

**对于二叉树，首先考虑遍历方式**

该题要求求解二叉树的最大深度，所以应该是遍历左子树的深度，然后遍历右子树的深度，选择最大深度加1

所以，是后序遍历（左右中），因为需要通过递归函数的返回值计算树的深度

**递归三部曲：**  
（1）确定递归函数的参数和返回值

> 参数：传入树的根节点  
> 返回值：返回树的深度

（2）确定终止条件

> 如果空间点，返回0，表示高度为0

（3）确定单层递归逻辑

> 先求左子树的高度，再求右子树的高度，最后取左右深度最大数值，然后再加1即可  
> 加一是因为算上当前中间节点

class Solution { 
        public int maxDepth(TreeNode root) { 
            return getDepth(root);
        }
    
        private int getDepth(TreeNode root) { 
            if (root==null){ 
                return 0;
            }
            //左子树的深度
            int leftDepth = getDepth(root.left);
            //右子树的深度
            int rightDepth = getDepth(root.right);
            //最大深度加1
            int depth = Math.max(leftDepth, rightDepth) + 1;
            return depth;
        }
    }

简化写法：

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

### 3. 迭代法 ###

借助层序遍历实现，因为最大深度就是二叉树的层数，和层序比那里的方式及其吻合

class Solution { 
        public int maxDepth(TreeNode root) { 
            if (root == null) { 
                return 0;
            }
            Deque<TreeNode> deque = new LinkedList<>();
            deque.add(root);
            int size;
            //记录层数
            int res = 0;
            TreeNode node;
            while (!deque.isEmpty()) { 
                size = deque.size();
                //遍历一层就加一
                res++;
                while (size > 0) { 
                    node = deque.poll();
                    if (node.left != null) { 
                        deque.add(node.left);
                    }
                    if (node.right != null) { 
                        deque.add(node.right);
                    }
                    size--;
                }
            }
            return res;
        }
    }

## 二、求解N叉树的最大深度 ##

### 1. 题目 ###

### 2. 递归法 ###

与二叉树的最大深度求解类似，二叉树是先遍历左子树的深度，再遍历右子树的深度

N叉树类似，遍历所有的子树，然后求其中的最大值加1

class Solution { 
        public int maxDepth(Node root) { 
            if (root == null) { 
                return 0;
            }
            int depth = 0;
            for (Node node : root.children) { 
                depth = Math.max(depth, maxDepth(node));
            }
            return depth + 1;
        }
    }

### 3. 迭代法 ###

依然采用层序遍历实现

class Solution { 
        public int maxDepth(Node root) { 
            if (root == null) { 
                return 0;
            }
            Deque<Node> deque = new LinkedList<>();
            deque.add(root);
            Node node;
            int size;
            int res = 0;
            List<Node> list;
            while (!deque.isEmpty()) { 
                size = deque.size();
                res++;
                while (size > 0) { 
                    size--;
                    node = deque.poll();
                    list = node.children;
                    for (Node n : list) { 
                        deque.add(n);
                    }
                }
            }
            return res;
        }
    }

## 三、总结 ##

二叉树，确定遍历顺序，

是先处理节点：前序

还是先遍历：中序或者后序

> 中序遍历顺序和处理顺序不一致，需要借助指针实现

结果是否由返回值确定：后序遍历

[20210513103828721.png]: /images/20221021/488e0c36ffdc41ce808ee99d51f5a4a9.png