c++ - 查找非二叉树的高度

Question

我在一个网站上做练习，在练习中我们必须通过实现一个函数来找到一个非二叉树的高度。我在下面有一个 TreeNode 类。

class TreeNode
{
public:
TreeNode();
TreeNode(string data);
void addChild(TreeNode* child);
vector<TreeNode*>& getChildren();
void setData(string data);
string getData();
void visit();
};

我实现了这个http://codepad.org/BiXkbABf。但这不起作用。我该如何实现这个功能？

Answer 1

循环内的逻辑是完全错误的。出于某种原因，您正在查看成对的连续孩子。相反，您应该一次只看一个孩子，然后选择一个身高最大的孩子。

Answer 2

此行有错误；尝试自己发现它：

if(k>maxi)k=maxi;

此外，尽管您的整体方法应该有效，但它执行的工作比必要的要多，因为大多数子树的高度几乎都被计算了两次。您可能希望重写代码以仅计算每个高度一次（提示：不要直接比较两个高度；相反，将前一个子树的高度存储在一个变量中，并仅将一个子树的高度与该变量进行比较）。

Answer 3

int hight(TreeNode* node) {
    vector<TreeNode*>& children = node.getChildren();
    unsigned int h = 0;
    for(int i = 0; i < children.size(); i++) {
        h = std::max(h, hight(children[i]));
    }
    return h + 1;
}

return 1 + maxi; 是一个错误。您已经考虑了当前节点k = 1 + max(height((tree->getChildren)()[i]),height((tree->getChildren)()[i+1]));

Answer 4

接下来将以下行放在源代码顶部；尝试弄清楚它们的用途并相应地修复您的代码

#include <algorithm>
using namespace std;