二叉树的深度和高度图解

二叉树是一种重要的数据结构，在计算机科学中被广泛应用，其深度和高度是其重要的性质之一。在本文中，我们将从多个角度分析什么是二叉树深度和高度，并通过图解的方式进行解释和说明。

什么是二叉树深度和高度？

深度是指从根节点到某个节点的路径长度，即路径上包含的边数。树的深度是指所有节点深度的最大值。高度是指从某个节点到根节点的路径长度，即路径上包含的边数。树的高度是指所有节点高度的最大值。

图解二叉树深度和高度

首先，我们来看一个简单的二叉树的例子，如下图所示：

1

/ \

2 3

/ \

4 5

从根节点1到节点4的路径长度是2，因此节点4的深度为2。同理，节点2和节点5的深度分别为1和2。树的深度为3。

从节点4到根节点1的路径长度是3，因此节点4的高度为3。同理，节点1和节点5的高度分别为1和2。树的高度为3。

接下来，我们来看一个稍微复杂一些的二叉树的例子，如下图所示：

1

/ \

2 3

/ \

4 5

/ \

6 7

从根节点1到节点6的路径长度是4，因此节点6的深度为4。同理，节点2和节点7的深度分别为2和3。树的深度为4。

从节点6到根节点1的路径长度是3，因此节点6的高度为3。同理，节点1和节点4的高度分别为1和2。树的高度为3。

如何求解二叉树深度和高度？

对于一个二叉树，求它的深度和高度有多种方法。常见的方法有递归和非递归两种。

递归方法

递归方法是一种较为简单的方法，通过递归实现深度和高度的求解。递归方法的核心思想是：一个节点的深度/高度等于其子节点中深度/高度的最大值加1。

具体的递归实现如下：

// 求解二叉树的深度

public int maxDepth(TreeNode root) {

if (root == null) {

return 0;

}

int leftDepth = maxDepth(root.left);

int rightDepth = maxDepth(root.right);

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

}

// 求解二叉树的高度

public int maxHeight(TreeNode root) {

if (root == null) {

return 0;

}

int leftHeight = maxHeight(root.left);

int rightHeight = maxHeight(root.right);

return Math.max(leftHeight, rightHeight) + 1;

}

非递归方法

非递归方法是一种较为高效的方法，通过栈来实现深度和高度的求解。

具体的非递归实现如下：

// 求解二叉树的深度（非递归）

public int maxDepth(TreeNode root) {

if (root == null) {

return 0;

}

Stack stack = new Stack<>();

Stack depthStack = new Stack<>();

int maxDepth = 0;

stack.push(root);

depthStack.push(1);

while (!stack.isEmpty()) {

TreeNode node = stack.pop();

int depth = depthStack.pop();

maxDepth = Math.max(maxDepth, depth);

if (node.left != null) {

stack.push(node.left);

depthStack.push(depth + 1);

}

if (node.right != null) {

stack.push(node.right);

depthStack.push(depth + 1);

}

}

return maxDepth;

}

// 求解二叉树的高度（非递归）

public int maxHeight(TreeNode root) {

if (root == null) {

return 0;

}

Stack stack = new Stack<>();

Stack heightStack = new Stack<>();

int maxHeight = 0;

stack.push(root);

heightStack.push(1);

while (!stack.isEmpty()) {

TreeNode node = stack.pop();

int height = heightStack.pop();

maxHeight = Math.max(maxHeight, height);

if (node.left != null) {

stack.push(node.left);

heightStack.push(height + 1);

}

if (node.right != null) {

stack.push(node.right);

heightStack.push(height + 1);

}

}

return maxHeight;

}

二叉树深度和高度的应用

二叉树深度和高度的应用非常广泛，如下列举几个例子：

- 用于求解二叉树的最大宽度和最小宽度；

- 用于判断二叉树是否为平衡二叉树；

- 用于优化二叉树的搜索和遍历算法。

本文所述的递归和非递归方法实现起来简单，而且时空复杂度都比较低，非常适用于二叉树深度和高度的求解。在实际应用中，我们可以根据不同的需求和情况选择采用递归和非递归方法。