二叉树的高度和深度

二叉树是一种常见的数据结构，它由节点和连接它们的边组成。每个节点最多有两个子节点，分别称为左子树和右子树。在二叉树中，我们经常要讨论两个概念：高度和深度。本篇文章将从多个角度对二叉树的高度和深度进行分析。

一、 高度和深度的定义

高度(h)和深度(d)是二叉树中最基本的概念。它们两者都是从根节点开始算起的。为了方便说明，下文中“深度”和“高度”会交替使用。我们先来定义一下它们：

1.高度：树的高度是指所有节点的最大深度，根节点的深度为0，第一层子节点的深度为1，以此类推。因此，一棵只有根节点的树的高度为0，一棵有n个节点的满二叉树的高度为log2(n+1)-1。

2.深度：一个节点的深度是指它到根节点的路径长度。根节点深度为0，其它节点深度为其父节点深度加1。

二、如何计算一棵二叉树的高度

有了定义之后，我们来看一下如何计算一棵二叉树的高度。假设root为根节点，height(root)为根节点的高度，left为左子树的根节点，height(left)为左子树的高度，right为右子树的根节点，height(right)为右子树的高度，则一棵树的高度可以递归地计算为：

```

height(root)=max(height(left), height(right)) + 1

```

这个递归公式的意义是找到整棵树的最深层数，而子树的深度可以通过相同的方式计算。因此，我们可以从根节点开始递归计算左右子树的高度，然后取两个子树中的最大值，并加上1，最终得到整个树的高度。

三、如何计算一棵二叉树的深度

计算一棵二叉树的深度非常简单，只需要对每个节点进行深度遍历，并计算出从根节点到该节点的路径长度即可。如果该节点比当前路径长度更深，则更新当前路径长度。

以下是二叉树深度遍历的Java代码：

```

public int findDepth(TreeNode root) {

if (root == null) {

return 0;

}

int leftDepth = findDepth(root.left);

int rightDepth = findDepth(root.right);

return Math.max(leftDepth, rightDepth) + 1;

}

```

四、高度与深度的应用

深度和高度是二叉树的基本概念，它们在很多算法中有广泛的应用。这里我们列出几个例子：

1.判断一棵二叉树是否平衡。如果一棵二叉树每个节点的左右子树高度差不超过1，则称其为平衡二叉树。可以利用计算深度和高度的方法来判断一棵二叉树是否平衡，时间复杂度为O(nlogn)。

2.优化搜索时间。在二叉搜索树中，如果我们能够估计出一个节点的深度或高度，就可以大大缩小搜索范围，从而优化搜索时间。

3.完美二叉树的存储空间。如果一棵二叉树是完美二叉树，则其节点总数n=2^h-1，因此可以用大小为n的数组来存储完美二叉树节点的值，查找速度极快。