如何编写无参数的二叉搜索树高度计算函数？

嘿，这个需求确实有点反直觉——毕竟咱们写树的递归操作时，习惯了把节点作为参数传递。不过别担心，咱们可以通过封装类成员变量的方式来实现无参数的高度函数，同时保留你原来的递归逻辑。

核心思路 #

你之前尝试在参数外声明root没成功，大概率是因为这个root不是函数能访问到的作用域变量（比如只是局部变量）。解决办法是把二叉搜索树的根节点root作为类的成员变量，这样无参数的高度函数作为类的方法，就能直接访问到根节点，再通过一个带参数的私有辅助函数完成递归逻辑（毕竟递归必须处理不同的子节点，参数还是少不了，但对外接口可以做到无参数）。

代码实现示例 #

先定义你的Node类（和原来的结构一致）：

class Node {
    int value;
    Node m_left;
    Node m_right;

    public Node(int value) {
        this.value = value;
        this.m_left = null;
        this.m_right = null;
    }
}

然后封装一个BinarySearchTree类，把root作为成员变量，对外提供无参数的height()方法：

class BinarySearchTree {
    private Node root;

    // 这里可以添加构造函数、插入节点等其他树操作方法
    public BinarySearchTree() {
        this.root = null;
    }

    // 对外的无参数高度计算函数
    public int height() {
        // 调用内部带参数的递归辅助函数，传入根节点
        return calculateSubtreeHeight(root);
    }

    // 私有辅助函数，负责递归计算子树高度（和你原来的逻辑几乎一致）
    private int calculateSubtreeHeight(Node node) {
        if (node == null) {
            return 0;
        }
        int hleftsub = calculateSubtreeHeight(node.m_left);
        int hrightsub = calculateSubtreeHeight(node.m_right);
        return Math.max(hleftsub, hrightsub) + 1;
    }
}

怎么使用？ #

当你创建二叉搜索树实例后，直接调用无参数的height()方法就行：

public class Main {
    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        // 先往树里插入节点...
        int treeHeight = bst.height(); // 无需传参，直接获取高度
        System.out.println("树的高度是：" + treeHeight);
    }
}

为什么不推荐全局变量？ #

你可能会想：直接把root设为全局变量行不行？理论上可以，但全局变量会带来副作用（比如递归过程中如果不小心修改了全局的root，会导致整个逻辑混乱），而且不符合面向对象的封装原则，所以更推荐用类成员变量的方式。

内容的提问来源于stack exchange，提问作者Wade Kemmsies