Binary tree -- 104. Maximum depth of binary tree

1 Title Description

Given a binary tree , Find out the maximum depth .

The depth of a binary tree is the number of nodes in the longest path from the root node to the farthest leaf node .

explain : A leaf node is a node that has no children .

2 Title Example

3 Topic tips

There is no hint in this question

4 Ideas

Method 1 : Depth-first search
If we know the maximum depth of the left and right subtrees Ⅰ and r, Then the maximum depth of the binary tree is
max(l, r)＋1
The maximum depth of left and right subtrees can be calculated in the same way . So we can use 「 Depth-first search 」 To calculate the maximum depth of the binary tree . To be specific , When calculating the maximum depth of the current binary tree , You can recursively calculate the maximum depth of its left and right subtrees , And then in O(1) Calculate the maximum depth of the current binary tree in time . Recursion exits when an empty node is accessed .
Complexity analysis
Time complexity :O(n), among n Is the number of binary tree nodes . Each node is recursively traversed only once .
Spatial complexity :O(height), among height Represents the height of the binary tree . Recursive functions require stack space , And stack space depends on the depth of recursion , So the space complexity is equivalent to the height of the binary tree .
Method 2 : Breadth first search
We can also use 「 Breadth first search 」 To solve this problem , But we need to — Some modifications , At this time, our breadth first search queue is 「 All nodes of the current layer 」. Every time you expand to the next level , Unlike breadth first search, only one node is taken out of the queue at a time , We need to expand all nodes in the queue , This ensures that all nodes of the current layer are stored in the queue every time the expansion is completed , That is, we expand layer by layer , Finally, we use a variable ans To maintain the number of expansions , The maximum depth of the binary tree is ans.
Complexity analysis
· Time complexity :O(n), among n Is the number of nodes in a binary tree . The same analysis as method 1 , Each node is accessed only once .
· Spatial complexity : The consumption of this method space depends on the number of elements stored in the queue , It will reach... In the worst case O(n).

5 My answer

Method 1 : Depth-first search

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

Method 2 ： Breadth first search

class Solution {
    
    public int maxDepth(TreeNode root) {
    
        if (root == null) {
    
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        int ans = 0;
        while (!queue.isEmpty()) {
    
            int size = queue.size();
            while (size > 0) {
    
                TreeNode node = queue.poll();
                if (node.left != null) {
    
                    queue.offer(node.left);
                }
                if (node.right != null) {
    
                    queue.offer(node.right);
                }
                size--;
            }
            ans++;
        }
        return ans;
    }
}