时间戳

首页 > 解决方案 > 二叉树的最大深度是否应该排除根？

data-structures - 二叉树的最大深度是否应该排除根？

问题描述

到目前为止，我在这里看到了树的最大深度的 2 种不同实现，

  1. 第一个，max depth === level - 1： https ://www.geeksforgeeks.org/write-ac-program-to-find-the-maximum-depth-or-height-of-a-tree/

    • 这意味着，对于基本情况，if !node: return -1
    • 所以三级树的最大深度为 2

  2. 第二个，max depth === level： https ://leetcode.com/problems/maximum-depth-of-binary-tree/

    • 这意味着，对于基本情况，if !node: return 0
    • 所以三级树的最大深度为 3

javascript中的实现就像这样简单：

function maxDepth(node){
   if (!node) return -1;
   return Math.max(maxDepth(node.left),maxDepth(node.right))+1;
}

哪一个是正确的？我在这里想念什么？

此外，树的最大深度等于树的高度，对吧？虽然它以不同的方式计算，深度是从节点到根，高度是从节点到叶节点。

标签： data-structurestreebinary-tree

解决方案

这些术语在不同的地方有不同的含义。因此，无论在何处使用，都应加以澄清。

对于根，级别 = 1，深度 = 0，高度 = 1。

级别 = 深度 + 1。

来源：http ://typeocaml.com/2014/11/26/height-depth-and-level-of-a-tree/

维基百科：

节点的高度是从该节点到叶子的最长向下路径的长度。根的高度就是树的高度。节点的深度是到其根的路径（即其根路径）的长度。这在操作各种自平衡树时通常需要，特别是 AVL 树。根节点的深度为零，叶节点的高度为零，只有一个节点的树（因此有根和叶）的深度和高度为零。按照惯例，一棵空树（没有节点的树，如果允许的话）的高度为 -1

关于树深度和高度之间有什么区别的另一个有趣的讨论？.

推荐阅读