题目:给定一个二叉树 root
,返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1:
输入:root = [3,9,20,null,null,15,7] 输出:3
示例 2:
输入:root = [1,null,2] 输出:2
解题思路+代码:
代码:
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public int maxDepth(TreeNode root) {/**思路:使用深度优先搜索(DFS)使用递归方法1.创建dfs方法(int型)2.判断根节点是否为空,为空高度返回03.遍历左右子树的高度,再使用Math.max取最大高度(需要加上根节点高度1)*/return dfs(root); //调用并返回最大高度}public int dfs(TreeNode node){if(node == null){return 0 ;}int leftTree = dfs(node.left); //遍历左子树高度 用int类型的leftTree接收int rightTree = dfs(node.right); //遍历右子树高度 用int类型的rightTree接收return Math.max(leftTree,rightTree) + 1; //Math.max取左右子树中最大高度,加上根节点的高度1}
}
总结:这道题明确了求最大深度,可以知道是使用二叉树的深度优先搜索(DFS)方法来解答。要求返回的高度是int型,因此所创建的方法也要是int型。方法中遍历左右子树的高度后,需要使用Math.max来取最大高度(注意:不能忘记根节点的高度)+1。