One 、 Title Description

Link to the original text ：104. The maximum depth of a binary tree


A detailed description ：
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 .

Two 、 Thought analysis

Once before The maximum depth of the binary number , In fact, it uses hierarchical traversal ！ This time we use recursion ！
First of all, let's understand a sentence ： Preorder traversal is depth , Post order traversal is depth , Depth equals height ！
From this sentence, we can see two solutions , A preamble , A post order ！
Let's talk about the sequence first （ Recursive Trilogy ）：

• Determine the parameters and return values , The return value is int Depth of type , Parameters are subtrees + depth
• Termination conditions , If the subtree is null Returns the current depth
• Single layer logic is , Traverse the left node , After traversing the right node , Compare the size ！

Let's talk about the preface （ Recursive Trilogy ）：

• Because the first root is on the left and right , So you can't return a value at the root , So the return value is void, Parameter or subtree + depth
• The termination condition is to find that if the left and right subtrees are empty, it will end
• Compare with the current depth and root to get the maximum value , Then recursively obtain the maximum value in the left and right subtrees ！

3、 ... and 、AC Code

After the sequence traversal ：

/** * 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) {
    
        return getDepth(root, 0);
    }
    public int getDepth(TreeNode root, int depth){
    
        if (root == null) return depth;
        int leftDepth = getDepth(root.left, depth + 1);//  Left 
        int rightDepth = getDepth(root.right, depth + 1);//  Right 
        return leftDepth > rightDepth ? leftDepth : rightDepth;//  root 
    }
}

The former sequence traversal ：

/** * 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 {
    
    int result = 0;
    public int maxDepth(TreeNode root) {
    
        if (root == null)  return result;
        getDepth(root, 1);
        return result;
    }
    
    public void getDepth(TreeNode root, int depth){
    
        result = result > depth ? result : depth;//  root 

        if (root.left != null){
    
            depth++;
            getDepth(root.left, depth);
            depth--;//  Return to the original value , Otherwise, the right subtree will be found on the basis of the left subtree ！
        }

        if (root.right != null){
    
            depth ++;
            getDepth(root.right, depth);
            depth--;
        }


        
    }
}

Four 、 summary

• depth = Height , Depth is from root to leaf node , Height is from leaf to root ！

5、 ... and 、 Consolidation exercises

• 559. N The maximum depth of the fork tree

/* // Definition for a Node. class Node { public int val; public List<Node> children; public Node() {} public Node(int _val) { val = _val; } public Node(int _val, List<Node> _children) { val = _val; children = _children; } }; */

class Solution {
    
    public int maxDepth(Node root) {
    
        return getDepth(root, 1);
    }
    public int getDepth(Node root, int depth){
    
        if (root == null) return 0;
        int maxDepth = depth;
        for (int i = 0; i < root.children.size(); i++){
    
            int tmpDepth = getDepth(root.children.get(i), depth + 1);
            maxDepth = tmpDepth > maxDepth ? tmpDepth : maxDepth;
        }
        return maxDepth;
    }
}

Thanks for reading , I am a Alson_Code, One likes to complicate simple problems , A program that simplifies complex problems ！