104. 二叉树的最大深度

2023-10-28 15:17| 来源: 网络整理| 查看: 265

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

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

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

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

3 / \ 9 20 / \ 15 7

返回它的最大深度 3 。

题意二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。根据树的定义可知,此题需要递归或者借助栈求解。树的定义

树是n个结点的有限集合。在任意一颗非空树中：（1）有且仅有一个特定的称为根（root）的结点；（2）当n>1时,其余结点可分为m(m>0)个互补相交的有限集合T1,T2,T3....Tm,其中每个集合本身又是一颗树,并且称为根的子树。

思路递归的思想是把大的问题，分解成小的同等的问题，最终会有一个终止条件，我们只需先序遍历整棵树，然后，每进入一层递归，树的深度就加1，然后比较当前结点（子树的根）的左右子树深度，选深度较大的与当前树的深度累加，退出当前递归调用。先序遍历

先根->左子树->右子树

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int maxDepth(TreeNode root) { int max=0;//存储子树的深度 int leftMax=0; int rightMax=0; if (root != null) {//如果当前子树不为空,非空树 max++;//深度加1 leftMax = maxDepth(root.left);//左子树深度 rightMax = maxDepth(root.right);//右子树深度 max += leftMax >= rightMax ? leftMax : rightMax;//当前子树的深度 } return max;//返回当前子树的深度 } } 总结主要是需要了解树的基本定义,和递归调用的原理。此题还有非递归版本，借助栈实现。其实方法递归调用也是同样的原理，jvm内存模型有个线程栈，有兴趣的同学可以自行了解。

【本文地址】

公司简介

联系我们