当前位置：首页 > news >正文

代码随想录刷题day41|（二叉树篇）二叉树的最大深度（递归）

news 2025/3/12 19:21:03

一、二叉树理论基础

二、二叉树的深度和高度

三、递归和迭代思路

3.1 递归法

3.2 迭代法

四、相关算法题目

五、总结

一、二叉树理论基础

详见：代码随想录刷题day34|（二叉树篇）二叉树的递归遍历-CSDN博客

二、二叉树的深度和高度

二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数；

二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数；

本题中，二叉树的最大深度=叶子节点的深度=从根节点到叶子节点的最长简单路径边的条数or节点数=根节点的高度；

一般求深度用前序遍历，求高度用后序遍历；

为什么？求深度，指的是该节点到根节点的距离，根节点的深度为1，往下逐渐递增，用前序遍历，中左右，逐步向下，层层向下，得到该节点的深度；

求高度，指的是该节点到叶子结点的距离，叶子结点的高度为1的话，往上逐渐递增，用后续，左右中，父节点根据左右孩子的高度再加1，层层向上返回，得到该节点的高度；

所以，求二叉树的最大深度就是求根节点的高度，故可以用后序遍历；

三、递归和迭代思路

3.1 递归法

1.确定递归函数的参数和返回值

参数：需要传入根节点，返回值是高度，int类型；

2.确定终止条件

node == null，返回0；

3.确定单层递归的逻辑

按照后序遍历，先处理左节点，递归遍历左节点，求出leftHight，接着递归遍历右节点，求出rightHight，两者取较大值，再加1，也即加上本节点node所在的高度，得出从该节点node到叶子节点的高度；

最后当node = root时，结果就是根节点到叶子节点的高度，也就是叶子节点的深度，即该二叉树的最大深度；

3.2 迭代法

层序遍历，详见：代码随想录刷题day38|（二叉树篇）二叉树的层序遍历（429、515、116、117、104、111）-CSDN博客

四、相关算法题目

104.二叉树的最大深度

class Solution {//递归法：后序遍历public int maxDepth(TreeNode root) {return getHight(root);}public int getHight(TreeNode node){//终止条件if(node == null) return 0;//单层递归的逻辑int leftHight = getHight(node.left);int rightHight = getHight(node.right);int hight = 1 + Math.max(leftHight, rightHight);return hight;}
}

559.N叉树的最大深度

思路：递归法同二叉树，不同点在于孩子节点的处理，没有左右节点之分，用增强for循环遍历所有孩子节点，并递归处理；

class Solution {public int maxDepth(Node root) {//递归法return getHight(root);}public int getHight(Node node){int max = 0;//记录当前节点的所有子节点的最大深度if(node == null) return 0;for(Node child : node.children){int childHight = getHight(child);max = Math.max(max, childHight);}int hight = 1 + max;return hight;}
}