package Leetcode.Trees;

/**
 * @author zhengstars
 * @date 2024/04/04
 */
public class MaximumDepthOfBinaryTree {
    public static int maxDepth(TreeNode root) {
        // if tree is empty, depth is 0
        if (root == null) {
            return 0;
        } else {
            // calculate maximum depth of left subtree
            int leftHeight = maxDepth(root.left);
            // calculate maximum depth of right subtree
            int rightHeight = maxDepth(root.right);
            // tree's maximum depth is maximum of left and right subtree depths plus 1
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }

    public static void main(String[] args) {
        // construct binary tree
        TreeNode root1 = new TreeNode(3);
        root1.left = new TreeNode(9);
        root1.right = new TreeNode(20);
        root1.right.left = new TreeNode(15);
        root1.right.right = new TreeNode(7);

        // find the maximum depth
        int depth1 = maxDepth(root1);
        // output: 3
        System.out.println(depth1);
    }
}