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

问：

这是计算二叉树高度的代码。我们假设所有节点值都是正 int。我使用了函数的递归。是否可以将成员函数组合成一个函数？对于一维情况（链表）很容易实现，但我对树一无所知。heightint 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;
            }
        }

C++ 树

@NathanOliver。我并不完全相信这是对的。这是一个（不是尾部可调用的）递归函数，运行在二叉树上，似乎不必平衡。在某些用例中，此函数很可能会溢出堆栈。将递归转换为迭代似乎是一件好事。（这就是我如何阅读他的问题实际上在问什么，但不清楚）

2赞 Holt 9/18/2019

@MikeVine 这并不是OP真正要问的......将两者合并到一个函数中不会使它成为尾递归函数，也不会使它成为迭代函数。height()height(TreeNode* root)

0赞 NathanOliver 9/18/2019

@MikeVine 通过正确的方法，我的意思是这样做的正确方法。是否应该使用递归是一个不同的问题。

0赞 Scott Hunter 9/18/2019

使用不使用其对象中任何信息的方法（第二个版本就是这种情况）究竟什么是“正确”的？height

答：

3赞 Scott Hunter 9/18/2019 #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所指出的，没有方法。我认为它应该，但这并没有使这个解决方案变得不那么不正确。TreeNodeheight

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

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

int height() {
    std::stack<std::pair<TreeNode *, int> > node_stack;
    node_stack.push(std::make_pair(root, 1));
    int height = 0;

    while (!node_stack.empty()) {
        auto node = node_stack.top();
        node_stack.pop();

        if (node.first) {
            height = std::max(height, node.second);
            node_stack.push(std::make_pair(node.first->left, node.second + 1));
            node_stack.push(std::make_pair(node.first->right, node.second + 1));
        }
    }

    return height;
}

class BinaryTree {
    inline static const TreeNode sentinel;
...
public:
int height(const TreeNode* root_in = &sentinel) const {
    if (root_in == &sentinel)
        return height(root); 

    if (!root_in)
        return 0;

    int lheight = height(root_in->left);
    int rheight = height(root_in->right);

    return std::max(lheight, rheight) + 1;
}

上一个：如何将 C# linq 中的 groupby 视为二维列表？

下一个：在某个区域中找到满意的单元格，然后突出显示该单元格所在的行

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

use one member function to calculate the height of a binary tree in C++

评论

评论

评论