c++ - C++中使用一个成员函数计算二叉树的高度

Question

下面是计算二叉树高度的代码。我们假设所有节点值都是正整数。我使用了 height 函数的递归。是否可以将成员函数 int height() 和 int height(TreeNode* root) 合并到一个函数中？对于一维情况(链表)很容易实现，但我不知道树。

    struct TreeNode
    {
        int val = 0;
        TreeNode *left = NULL;
        TreeNode *right = NULL;
        TreeNode(int val): val(val){}
    };

    struct BinaryTree
    {
        TreeNode *root;
        BinaryTree(TreeNode *root) : root(root) {}

        int height() {
            return height(root);
        }

        int height(TreeNode* root) {
            if (!root)
            {
                return 0;
            }
            else
            {
                int lheight = height(root->left);
                int rheight = height(root->right);

                return lheight > rheight ? lheight + 1 : rheight + 1;
            }
        }

Answer 1

我认为这就是您的要求；它只是使用计算树自身在子树上的高度的方法，而不是调用方法来计算任意树在子树上的高度。

int height() {
    if (!root)
    {
        return 0;
    }
    else
    {
        int lheight = root->left  ? root->left.height()  : 0;
        int rheight = root->right ? root->right.height() : 0;
        return lheight > rheight ? lheight + 1 : rheight + 1;
    }
}

更新:正如@Gupta 指出的，TreeNode 没有height 方法。我认为它应该，但这并没有使这个解决方案不正确。

这是一个可以添加到TreeNode的版本:

int height() {
    int lheight = left ? left.height() : 0;
    int rheight = right ? ight.height() : 0;
    return std::max(lheight, rheight) + 1;
}