怎么求出python二叉樹的最大深度

發(fā)布時間：2021-12-13 16:04:40 來源：億速云閱讀：161 作者：柒染欄目：大數(shù)據(jù)

本篇文章為大家展示了怎么求出python二叉樹的最大深度，內容簡明扼要并且容易理解，絕對能使你眼前一亮，通過這篇文章的詳細介紹希望你能有所收獲。

題目描述

給定一個二叉樹，找出其最大深度。

二叉樹的深度為根節(jié)點到最遠葉子節(jié)點的最長路徑上的節(jié)點數(shù)。

說明: 葉子節(jié)點是指沒有子節(jié)點的節(jié)點。

示例：給定二叉樹 [3,9,20,null,null,15,7]，

返回它的最大深度 3 。

解題方案

思路

標簽：DFS
找出終止條件：當前節(jié)點為空
找出返回值：節(jié)點為空時說明高度為0，所以返回0；節(jié)點不為空時則分別求左右子樹的高度的最大值，同時加1表示當前節(jié)點的高度，返回該數(shù)值
某層的執(zhí)行過程：在返回值部分基本已經(jīng)描述清楚
時間復雜度：O(n)

代碼

Java版本

/**
 * 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;
        }
    }
}

JavaScript版本

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    if(!root) {
        return 0;
    } else {
        const left = maxDepth(root.left);
        const right = maxDepth(root.right);
        return Math.max(left, right) + 1;
    }
};