网站开发pc端和手机端,赣州市官网,如何快速新建一个网站,58同城泰安题目 给定一个二叉树 root #xff0c;返回其最大深度。二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 示例 示例 1#xff1a;
输入#xff1a;root [3,9,20,null,null,15,7]
输出#xff1a;3示例 2#xff1a;
输入#xff1a;root [1,null,…题目 给定一个二叉树 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;StackTreeNode stack new StackTreeNode();StackTreeNode stack2 new StackTreeNode();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 StackTreeNode();i;}}return i;}
}
