求给定二叉树的最大深度,
深度是指树的根节点到任一叶子节点路径上节点的数量。
最大深度是所有叶子节点的深度的最大值。
(注:叶子节点是指没有子节点的节点。)
数据范围:,树上每个节点的val满足
要求: 空间复杂度 ,时间复杂度
要求: 空间复杂度 ,时间复杂度
public int maxDepth (TreeNode root) { // write code here if(root==null){ return 0; } return 1+Math.max(maxDepth(root.left) ,maxDepth(root.right)); }
public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param root TreeNode类 * @return int整型 */ public int maxDepth (TreeNode root) { // write code here return process(root); } public static int process(TreeNode root) { if (root == null) { return 0; } int r = process(root.right); int l = process(root.left); return Math.max(r, l)+1; } }
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param root TreeNode类 * @return int整型 */ public int maxDepth (TreeNode root) { // write code here if (root == null) { return 0; } else { int maxDepthLeft = maxDepth(root.left); int maxDepthRight = maxDepth (root.right); return 1 + Math.max(maxDepthLeft, maxDepthRight); } } }
public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param root TreeNode类 * @return int整型 */ public int maxDepth (TreeNode root) { // write code here if (root == null) { return 0; } return 1 + Math.max(maxDepth(root.left), maxDepth(root.right)); } }
public class Solution { /** * 求给定二叉树的最大深度 * * * @param root TreeNode类 * @return int整型 */ public int maxDepth (TreeNode root) { if (null == root) { return 0; } int leftDeep = maxDepth(root.left); int rightDeep = maxDepth(root.right); return Math.max(leftDeep, rightDeep) + 1; } }
public int maxDepth (TreeNode root) { List<Integer> list=new ArrayList<>(); Deque<TreeNode> qu=new LinkedList<>(); if(root==null) return 0; qu.offer(root); int depth=0; while(!qu.isEmpty()){ List<Integer> levelList=new ArrayList<>(); int level=qu.size(); for(int i=0;i<level;i++){ TreeNode peek=qu.peekFirst(); levelList.add(qu.poll().val); if(peek.left!=null) qu.offerLast(peek.left); if(peek.right!=null) qu.offerLast(peek.right); } //遍历完一层 depth++; } return depth; }
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public class Solution { private int maxDeep = 0; /** * * @param root TreeNode类 * @return int整型 */ public int maxDepth (TreeNode root) { dfs(root); return this.maxDeep; } public int dfs(TreeNode node) { if (node == null) { return 0; } int leftMax = Math.max(0, dfs(node.left)); int rightMax = Math.max(0, dfs(node.right)); this.maxDeep = Math.max(this.maxDeep, Math.max(leftMax, rightMax) + 1); return Math.max(leftMax, rightMax) + 1; } }
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public class Solution { /** * * @param root TreeNode类 * @return int整型 */ public int maxDepth (TreeNode root) { // write code here if (root == null) { return 0; } return doGetMaxDepth(root, 0); } private int doGetMaxDepth(TreeNode root,int depth) { if (root == null){ return depth; } int l = doGetMaxDepth(root.left, depth+1); int r = doGetMaxDepth(root.right, depth+1); return Integer.max(l, r); } }
public class Solution { /** * * @param root TreeNode类 * @return int整型 */ public int maxDepth (TreeNode root) { // root为空,返回深度0 if(root == null){ return 0; } // 向左子树遍历查找,拿到深度 int l = maxDepth(root.left); // 向右子树遍历查找,拿到深度 int r = maxDepth(root.right); // 返回 左子树 和 右子树 的深度取Max + 1 // +1的原因是 加上当前层 return Math.max(l,r) + 1; } }
int count = 0; int max = count; public int maxDepth (TreeNode root) { // write code here dfs(root); return max; } public void dfs(TreeNode root) { if (root == null) { return; } count++; dfs(root.left); if(count>max){ max = count; } dfs(root.right); if(count>max){ max = count; } count--; }
public int maxDepth (TreeNode root) { // write code here if (root == null) { return 0; } return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1; }
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public class Solution { /** * * @param root TreeNode类 * @return int整型 */ public int maxDepth (TreeNode root) { // write code here return null==root?0:Math.max(maxDepth(root.left),maxDepth(root.right)) + 1; } }
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public class Solution { /** * * @param root TreeNode类 * @return int整型 */ public int maxDepth (TreeNode root) { // write code here if (root == null) return 0; int left = maxDepth(root.left); int right = maxDepth(root.right); return left > right ? left + 1 : right + 1; } }
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public class Solution { /** * * @param root TreeNode类 * @return int整型 */ int r = 1; public int maxDepth (TreeNode root) { // write code here if(root == null) return 0; preorder(root, 1); return r; } public void preorder(TreeNode root, int d){ if(root != null){ if(d > r) r = d; preorder(root.left, d+1); preorder(root.right, d+1); } } // public int maxDepth (TreeNode root) { // // write code here // if(root == null) return 0; // return 1+Math.max(maxDepth(root.left), maxDepth(root.right)); // } }