这题我今天做contest的时候突然想起来，可以遍历一遍来做。。感觉时间复杂度跟经典的三行做法是一样的O(n)。。不过代码很冗长。
My code
int max = 0;
public int maxDepth(TreeNode root) {
traverse(root, 1);
return max;
}
private void traverse(TreeNode root, int lvl) {
if (root == null) return;
max = Math.max(lvl, max);
traverse(root.left, lvl + 1);
traverse(root.right, lvl + 1);
}
三行做法：
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
// + 1代表根节点
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
iteration 做法
如果做minimum depth，用这个方法复杂度低。
public int maxDepth(TreeNode root) {
if (root == null) return 0;
//本层的node数
int curNum = 1;
//下一层的node数
int nextNum = 0;
int level = 0;
LinkedList<TreeNode> linkedList = new LinkedList<>();
linkedList.add(root);
while (linkedList.size() != 0) {
TreeNode node = linkedList.poll();
curNum--;
if (node.left != null) {
linkedList.add(node.left);
nextNum++;
}
if (node.right != null) {
linkedList.add(node.right);
nextNum++;
}
if (curNum == 0) {
level++;
curNum = nextNum;
nextNum = 0;
}
}
return level;
}
