编程知识 cdmana.com

The maximum depth of binary tree (Java implementation)

Title Description

Given a binary tree , Find out the maximum depth .

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 .

source : Power button (LeetCode) link :https://leetcode-cn.com/problems/maximum-depth-of-binary-tree

Their thinking

If we know the maximum depth of the left and right subtrees l and r, Then the maximum depth of the binary tree is max(l,r)+1

The maximum depth of left and right subtrees can be calculated in the same way . So when we calculate the maximum depth of the current binary tree , You can recursively calculate the maximum depth of its left and right subtrees , And then in O(1) Calculate the maximum depth of the current binary tree in time . Recursion exits when an empty node is accessed .

Solution code

Complexity analysis

Time complexity :O(n), among n Is the number of binary tree nodes . Each node is recursively traversed only once .
Spatial complexity :O(height), among height Represents the height of the binary tree . Recursive functions require stack space , And stack space depends on the depth of recursion , So the space complexity is equivalent to the height of the binary tree .

/**
 * 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) {
        return depth(root);
    }

    public int depth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int l = depth(root.left) + 1;
        int r = depth(root.right) + 1;
        return l > r ? l : r;
    }
}

版权声明
本文为[Cheng Yu]所创,转载请带上原文链接,感谢

Scroll to Top