如何获得一棵二叉树的高度？

什么是二叉树的高度？

二叉树是一种特殊的数据结构，每个节点最多只有两个子节点。二叉树中有一个重要的指标——高度，用来衡量一棵树的复杂程度。高度定义为从根节点开始一直到叶子节点的最长路径，也就是根节点到叶子节点的最大深度。

如何递归获取二叉树的高度？

递归的方法是获取一棵二叉树高度的常见方式。可以创建一个递归函数来计算二叉树的高度。函数接受一个二叉树的根节点作为参数，然后检查根节点是否为空。为空则返回0，否则继续递归，分别计算左子树和右子树的高度，加1（因为要加上根节点）得到最终结果。代码如下： ```html function getHeight(node){ if (node === null) { return 0; } else { let heightLeft = getHeight(node.left); let heightRight = getHeight(node.right); return Math.max(heightLeft, heightRight) + 1; } } ```

如何使用BFS算法获得二叉树的高度？

另外一种获取二叉树高度的方法是使用BFS算法。BFS算法是广度优先搜索，是从根节点开始依次遍历每一层节点，直到找到目标节点或者遍历完所有节点。对于计算一棵二叉树的高度来说，BFS算法的具体实现可以是：从根节点开始，将根节点放入一个队列中，然后计数器设为0。之后每次从队列中取出一层的节点，将其左右节点放入队列中，计数器加1。最后遍历完所有的节点即可得到树的高度。 代码如下： ```html function getHeight(root){ if (root === null) { return 0; } let height = 0; let queue = [root]; while (queue.length > 0) { let levelSize = queue.length; for (let i = 0; i < levelSize; i++) { let currentNode = queue.shift(); if (currentNode.left) { queue.push(currentNode.left); } if (currentNode.right) { queue.push(currentNode.right); } } height++; } return height; } ```

总结

获取一棵二叉树的高度是一个比较基础的算法问题，适用于初学者的练习和面试题目。主要有两种方法：递归和BFS算法。其中，递归算法是比较经典的方式，BFS算法相对来说更直观易懂。无论是哪种方法，都需要注意边界条件的判断。同时，需要注意在面试时，面试官不仅关心算法本身，还会关心代码风格和可读性。