NO.104 二叉树的最大深度 简单
思路一:深搜 最直接的想法深搜。
1 2 3 4 5 6 7 8 9 10 11 12 13
| public int maxDepth(TreeNode root) { return dfs(root); }
private int dfs(TreeNode root) { if (root == null) return 0; int max1 = 0, max2 = 0; max1 += dfs(root.left); max2 += dfs(root.right); return Math.max(max1, max2) + 1; }
|
时间复杂度:O(n) 像是前序遍历。
思路二:广搜 广搜也是可以的,层序遍历,每遍历一层深度+1。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| public int maxDepth(TreeNode root) { int depth = 0; if (root == null) return depth; Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { depth++; int size = queue.size(); for (int i = 0; i < size; i++) { TreeNode poll = queue.poll(); if (poll.left != null) queue.add(poll.left); if (poll.right != null) queue.add(poll.right); } } return depth; }
|
时间复杂度:O(n) 层序遍历。
本人菜鸟,有错误请告知,感激不尽!
更多题解和源码:github