[leetcode] maximum depth of binary tree

104. The maximum depth of a binary tree

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 .

Example ：
Given binary tree  [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

Return to its maximum depth  3 .

Method 1 ： Depth-first search

Ideas and algorithms

If we know the maximum depth of the left and right subtrees ll and rr, 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)O(1) Calculate the maximum depth of the current binary tree in time . Recursion exits when an empty node is accessed .

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
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;

        }

    }
}