The title information

Subject address: leetcode-cn.com/problems/ma…

Given a binary tree, find its maximum depth. The depth of a binary tree is the number of nodes along the longest path from the root node to the farthest leaf node.

Note: Leaf nodes are nodes that have no child nodes.

Example:

Given a binary tree [3.9.20.null.null.15.7].3
   / \
  9  20
    /  \
   15   7Returns its maximum depth3 。
Copy the code

An overview of the

In fact, the first problem in the beginning of the tree is relatively simple, but its purpose is to give us a preliminary understanding of the tree such a structure. Each node in a binary tree has two children, two Pointers. The general structure is as follows:

public class TreeNode {
    // Node content value
    int val;
    // Two Pointers
    TreeNode left;
    TreeNode right;
    // constructor
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right; }}Copy the code

Solution 1: Depth-first Search (DFS)

Recursive idea, maximum depth = 1 + Max(L0(left), L0(right)). And each subtree finds its maximum depth. This is the process shown in the picture below, where you omit some things and only draw a part of it

public int maxDepth(TreeNode root) {
    / / export
    if(root == null) return 0;
    return Math.max(this.maxDepth(root.left), this.maxDepth(root.right)) + 1;
}
Copy the code

Time complexity: O(n), traversing n nodes

Space complexity: O(n), depending on depth, it’s not a balanced tree so it’s just less than n

Solution 2: Breadth-first Search (BFS)

Above is recursive, here is an iterative approach, input the root node determine whether there exists the depth + 1, and then determine the next layer of nodes (input layer 1 two nodes) of a node to judge any child nodes, no out, have the child nodes to add it again, note that there is a first in first out (line) because it is the relationship between layers and layers of traversal

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    int result = 0;
    while(! queue.isEmpty()) {// Traversal of each node in each layer
        for(int i = quene.size(); i > 0; i--){
            TreeNode node = queue.poll();
            if(node.left ! =null) queue.offer(node.left);
            if(node.right ! =null) queue.offer(node.right);
        }
        result++;
    }
    return result;
}
Copy the code

Time complexity: O(n), also traversing n nodes

Space complexity: O(n), using queues is also n in the worst case

conclusion

The first tree in the collection, generally familiar with the basic structure of the tree, experience tree traversal operation is very important, especially beginners to practice a variety of traversal.