24 | 二叉树基础（下）：有了如此高效的散列表，为什么还需要二叉树？
作者：鲁米
- 2023-12-09 北京
本文字数：1181 字
阅读完需：约 4 分钟
今天我讲了二叉树高度的理论分析方法，给出了粗略的数量级。如何通过编程，求出一棵给定二叉树的确切高度呢？
递归方法
class TreeNode { int val; TreeNode left; TreeNode right;
public TreeNode(int val) { this.val = val; }
}
public class BinaryTreeHeight {
public static int getHeight(TreeNode root) { if (root == null) { return 0; } int leftHeight = getHeight(root.left); int rightHeight = getHeight(root.right); // 返回左右子树中较大高度加上当前节点的高度（1） return Math.max(leftHeight, rightHeight) + 1; } public static void main(String[] args) { // 示例二叉树 TreeNode root = new TreeNode(1); root.left = new TreeNode(2); root.right = new TreeNode(3); root.left.left = new TreeNode(4); root.left.right = new TreeNode(5); int height = getHeight(root); System.out.println("二叉树的高度为：" + height); }
}
复制代码
迭代方法
import java.util.LinkedList;import java.util.Queue;
class TreeNode { int val; TreeNode left; TreeNode right;
public TreeNode(int val) { this.val = val; }
}
public class BinaryTreeHeight {
public static int getHeight(TreeNode root) { if (root == null) { return 0; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int height = 0; while (!queue.isEmpty()) { int levelSize = queue.size(); for (int i = 0; i < levelSize; i++) { TreeNode current = queue.poll(); if (current.left != null) { queue.offer(current.left); } if (current.right != null) { queue.offer(current.right); } } // 每层遍历结束后，高度加一 height++; } return height; } public static void main(String[] args) { // 示例二叉树 TreeNode root = new TreeNode(1); root.left = new TreeNode(2); root.right = new TreeNode(3); root.left.left = new TreeNode(4); root.left.right = new TreeNode(5); int height = getHeight(root); System.out.println("二叉树的高度为：" + height); }
}
复制代码
划线
评论
复制
发布于: 刚刚阅读数: 4
鲁米
关注
生活黑客35 2019-06-11 加入
起点不重要，迭代很重要，就需要保持充分的开放和积累；而信息越充分，结果越可靠，又要求随时调整、不断逼近真相。
评论