LeetCode 104. Maximum Depth of Binary Tree

Question

Given the root of a binary tree, return its maximum depth.

A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

https://leetcode.com/problems/maximum-depth-of-binary-tree/

Solution

• Solution1 – DFS, bottom up

class Solution {
   public int maxDepth(TreeNode root) {
        if (root == null){
            return 0;
        }
        return 1 + Math.max(maxDepth(root.left),maxDepth(root.right));
    }
}

bottom up general steps:
1. Base case
2. 向子问题要答案
3. 利用子问题构建当前答案
4. 额外操作
5. 返回答案给父问题

Complexity:

Time complexity: O(n)

Space complexity: O(n)