This is the 8th day of my participation in the August More text Challenge. For details, see: August More Text Challenge

Hello, everyone, today is the 8th day I participated in the August more text, today brings you about the binary tree related algorithm problem is to find the maximum depth of binary tree, the text is as follows:

Topic:

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: A leaf node is a node with no child nodes.

Example:

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

Returns its maximum depth of 3.

Their thinking

A. how deep b. how deep C. how deep D. how deep

Here we use the idea of recursion, we let the left subtree calculate the depth of the left subtree, and the right subtree calculate the depth of the right subtree.

According to the recursive trilogy:

  1. Determine the arguments and return values of the recursive function: the argument is the root node of the passed tree, and the return returns the depth of the tree, so the return value is int.

  2. End condition: returns 0 if the node is empty (this method also handles the case where the binary root node is empty).

  3. The main function of recursion function: first find the depth of the left subtree, then find the depth of the right subtree, and finally take the maximum value of the left and right depth and then +1 (because the current middle node is counted), which is the depth of the tree whose current node is the root node.

Code implementation

/** * 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 root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1; }}Copy the code

The last

Complexity analysis

  • Time complexity: O(n), where n is the number of nodes in the binary tree. As with method 1, each node is accessed only once.

  • Space complexity: The amount of space consumed by this method depends on the number of elements stored in the queue, which can reach O(n) in the worst case.