在本教程中，我们将讨论二叉树。
我们将看到如何递归和迭代地计算树数据结构的高度。

二叉树

二叉树是一种数据结构，其中的数据是以分层方式而不是线性方式存储的(就像在LinkedList和Arrays中那样)。

二叉树数据结构由节点组成。
每个节点都保存数据以及对子指针(左和右)的引用。

二叉树的根是最顶层的节点。
(与实际的活树相反)。

以下是带有某些节点的树的图示。

节点的高度是从该节点到叶子的最长的向下路径的长度。
根的高度是树的高度。

因此，为了计算树的高度，我们需要遍历树的每个节点以获得所有排列和组合。

有两种计算树高的方法。

• 递归方式
• 迭代方式

树的高度–递归

递归涉及计算子问题的结果，并将其返回给父问题。

涉及的步骤：

• 要递归计算树的高度，我们需要递归地找到它的左子树和右子树的高度，并将它们的值加1(最高节点及其子节点之间的高度)。

• 这些子树中的每个子树本身都可以具有左右子树，因此递归将一直应用到子树为NULL为止。
  空树节点的高度为-1。

• 最后，我们将比较左右子树的高度，并返回更大的树。

下图显示了计算二叉树高度的排列数量。

让我们编写Java程序来递归计算树的高度。
首先，我们将对Tree数据结构进行基本的实现。

package com.theitroad.tree.height;

public class BinaryTree {

	TreeNode root;

	public static class TreeNode {

		TreeNode left;
		TreeNode right;
		Object data;

		TreeNode(Object data) {
			this.data = data;
			left = right = null;
		}
	}
}

我们来看一下使用递归查找树的高度的代码。

package com.theitroad.tree.height;

import com.theitroad.tree.height.BinaryTree.TreeNode;

public class HeightOfTree {

	public static void main(String[] args) {

		BinaryTree binaryTree = new BinaryTree();

		/**
		 * Binary Tree in our example, height = 2
		 * 		1		(Root)
		 * 	  2	  3		(Level 1)
		 *  4    	 5		(Level 2)
		 */
		binaryTree.root = new TreeNode(1);
		binaryTree.root.left = new TreeNode(2);
		binaryTree.root.right = new TreeNode(3);
		binaryTree.root.left.left = new TreeNode(4);
		binaryTree.root.right.left = new TreeNode(5);

		int heightOfTree = height(binaryTree.root);
		System.out.printf("Height of tree is %d", heightOfTree);
	}
	
	public static int height(TreeNode root) {

		if (root == null)
			return -1;

		int leftHeight = height(root.left);
		int rightHeight = height(root.right);

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

因此，在上面的代码中，一旦到达最底层的子节点，便将其加到树的高度，然后将结果返回到上一个调用。

输出：树的高度为2

现在，让我们以非递归方式执行相同的操作。

树的高度–迭代

要迭代计算树的高度，我们只需要计算树中的级别数。

涉及的步骤

• 创建一个队列，并将树的根添加到其中。

• 从队列中弹出节点并遍历队列，同时将子节点添加到队列中。

• 在每个迭代弹出窗口中，最新元素添加到队列中，并将下一级元素(此元素)添加到队列中。

• 这样做直到队列大小变为零。
  那将意味着下一级别具有零个元素。

• 对于每个遍历的级别，添加1。

以下是计算树的高度的迭代程序。

public static int heightIteratively(TreeNode root) {

  if (root == null)
      return -1;

  Queue<TreeNode> queue = new LinkedList<>();
  queue.add(root);
  int height = -1;

  while (!queue.isEmpty()) {
      int size = queue.size();

      height++;

      while (size > 0) {
          TreeNode treeNode = queue.remove();

          if (treeNode.left != null)
              queue.add(treeNode.left);

          if (treeNode.right != null)
              queue.add(treeNode.right);
          
          size--;
      }
  }
  return height;
}

上面的代码一直运行，直到队列不为空。
而且，它会在从队列中删除当前级别项目的同时，继续在下一级别添加所有元素。

时间复杂度为O(n)。
空间复杂度为O(1)。