- 题目
给定一个二叉树 root ,返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
- 示例
示例 1: 输入:root = [3,9,20,null,null,15,7] 输出:3 示例 2: 输入:root = [1,null,2] 输出:2
- 解题思路
- 方法一:递归。(深度优先)
- 树的深度,等于子树的深度加1。
- 那么求二叉树的最大深度,也就是求其左子树和右子树深度的最大值。
- 方法二:层遍。(广度)
- 从根节点开始,依次遍历每一层的所有节点,那么深度+1。遍历后,将当前层节点的所有子树都作为根节点,继续遍历下一层。
- 使用额外内存存储当前层节点。
- 方法一:递归。(深度优先)
- 代码(Java)
// 方法一 class Solution { public int maxDepth(TreeNode root) { if (root == null) { return 0; } int maxLeft = maxDepth(root.left); int maxRight = maxDepth(root.right); return Math.max(maxLeft, maxRight) + 1; } }
// 方法二 class Solution { public int maxDepth(TreeNode root) { if (root == null) { return 0; } int i = 1; Stack<TreeNode> stack = new Stack<TreeNode>(); Stack<TreeNode> stack2 = new Stack<TreeNode>(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); if (node.left != null || node.right != null) { if (node.left != null) { stack2.push(node.left); } if (node.right != null) { stack2.push(node.right); } } if (stack.isEmpty() && !stack2.isEmpty()) { stack = stack2; stack2 = new Stack<TreeNode>(); i++; } } return i; } }
【LeetCode热题100】104. 二叉树的最大深度(二叉树)
2024-03-11 18:40:05 21 阅读