Cabbage Java self study room covers core knowledge

104. Maximum depth of binary trees LeetCode Series (Java edition) 111. The minimum depth of a binary tree

Force buckles the original problem

104. Maximum depth of a binary tree

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: Leaf nodes are nodes that have no child nodes.

Example:

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

    3
   / \
  9  20
    /  \
   15   7
Copy the code

Returns its maximum depth of 3.

Their thinking

  • Implementation: DFS (depth-first search)
  • Find the termination condition: the current node is empty
  • If the node is null, the height is 0, so 0 is returned. If the node is not empty, the maximum height of the left and right subtrees is calculated respectively, and the value is returned by adding 1 to indicate the height of the current node
  • The execution of a layer is described in the return value section

Code implementation

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int maxDepth(TreeNode root) { if(root == null) { return 0; } else { int left = maxDepth(root.left); int right = maxDepth(root.right); return Math.max(left, right) + 1; }}}Copy the code

Complexity analysis

  • Time complexity: O(n)O(n)O(n), where NNN is the number of nodes in the binary tree. In the same analysis as method 1, each node is accessed only once.

  • Space complexity: The consumption of space for this method depends on the number of elements in the binary tree, which in the worst case reaches O(n)O(n)O(n).

104. Maximum depth of binary trees LeetCode Series (Java edition) 111. The minimum depth of a binary tree