铭记:

源码下载

方法一：递归

核心思想：树的高度由左子树或右子树中的最大那个树的高度+1

    /**
     * 递归求 二叉树 高度
     * 树的高度，取决于树的左子树和右子树的高度
     * @param node 节点
     */
    private int treeHeightWithRecursion(RavenNode node) {
        if (node == null) return 0;
        return 1 + Math.max(treeHeightWithRecursion(node.leftNode), treeHeightWithRecursion(node.rightNode));
    }

方法二：非递归

核心思想：通过层序遍历来获得二叉树高度；让二叉树依次入队，然后循环遍历这个队列，直到队列为空，把每一层的元素都记录下来num，在遍历的过程中，每循环一次num--，当num==0时代表该层的元素都已经出队了，那么此时在队列中的元素都是下一层的元素，所以把队列的个数赋值给num，继续上面的过程

    /**
     * 非递归方式求二叉树高度
     *
     * @param node
     * @return
     */
    private int treeHeightWithNonRecursion(RavenNode node) {
        if (rootNode == null) return 0;
        int height = 0;
        int rowNum = 1;
        Queue<RavenNode> queue = new LinkedList<>();
        queue.add(rootNode);
        while (!queue.isEmpty()) {
            RavenNode peek = queue.remove();
            if (peek.leftNode != null) {
                queue.add(peek.leftNode);
            }
            if (peek.rightNode != null) {
                queue.add(peek.rightNode);
            }
            rowNum--;
            if (rowNum == 0) {
                // 层数+1
                height++;
                // 重新记录层的元素
                rowNum = queue.size();
            }
        }
        return height;
    }