How to find the maximum depth of a binary tree in Java (with code)

The content of this article is about how to achieve the maximum depth of a binary tree in Java (with code). It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.

Given a binary tree, find its maximum depth.

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

#Explanation: A leaf node refers to a node that has no child nodes.

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

3
/ \
9 20
/ \
15 7

Returns its maximum depth of 3.

Master the use of trees through this question

Question analysis: Find the depth of a binary tree;

You can browseBasic concepts of binary trees at a glance to further understand binary trees;

We also use recursive methods to solve this problem, the root node is not Empty, we recursively traverse the left subtree and the right subtree to see which subtree has more levels, and finally traverse until the leaf node is reached;

Use a Technical implementation of the statement: return nleft > nright ? nleft 1 : nright 1;

Take this binary tree as Example:

3
/ \
9 20
/ \
15 7

1. This tree is not empty

2. Recursively traverse the left subtree of this tree: the left subtree is not empty; both the left subtree and the right subtree of the left subtree are empty, then 0 is returned for judgment, 0 == 0, the left subtree of this tree returns 0 1 = 1;

3. Recursively traverse the right subtree of this tree: the right subtree is not empty; the right subtree The left subtree and right subtree of the tree are not empty; recursively traverse the left subtree of the right subtree and the right subtree of the right subtree; the left subtree and right subtree of the left subtree of the right subtree are empty, and return 0 , the left subtree and right subtree of the right subtree of the right subtree are empty, return 0, make a judgment, 0 == 0, then the left subtree and right subtree of the right subtree of this tree return 0 1 = 1 , judge 1 == 1, then the right subtree of this tree returns 1 1 = 2;

4. Compare the left subtree and the right subtree, 1 < 2 , then this tree returns 2 1 = 3, then the depth of this tree, that is, the number of layers, is 3.

In fact, the main idea of ​​this method is: as long as it is recursively traversed until For the leaf nodes of this tree, in the end, as long as the leaf node is traced back to the root node and merged to 1, the result is the length of the path passed by the trace back 1.

Code implementation:

public static class TreeNode
    {
        int data;
        TreeNode left;
        TreeNode right;
        TreeNode(int val)
        {
            data = val;
        }
    }

    public int maxDepth(TreeNode root)
    {
        if (root == null)
            return 0;

        int nleft = maxDepth(root.left);
        int nright = maxDepth(root.right);

        return nleft > nright ? nleft + 1 : nright + 1;
    }

Main function:

public static void main(String[] args)
    {
        TreeNode p = new TreeNode(1);
        p.left = new TreeNode(2);
        p.right = new TreeNode(3);
        p.left.left = null;
        p.left.right = null;
        p.right.left = new TreeNode(4);
        p.right.right = new TreeNode(5);

        Tree1 t = new Tree1();
        System.out.println(t.maxDepth(p));
    }

Run result: 3

The above is the detailed content of How to find the maximum depth of a binary tree in Java (with code). For more information, please follow other related articles on the PHP Chinese website!