计算二叉树的高度作为void函数

Question

我正在学习 C++ 并尝试编写一个 void 函数来计算节点的高度。该函数必须是 void 类型，因此它不能 return 任何东西，但应该正确计算节点的高度。下面是我的代码：

void computeHeight(Node *n) {

  if (!n->left && !n->right){
    n->height = 0;
  }
  else if (n->left && !n->right){
    n->height = 1 + computeHeight(n->left);
  }
  else if (!n->left && n->right){
    n->height = 1 + computeHeight(n->right);
  }
  else {
    if (computeHeight(n->left) > computeHeight(n->right)){
      n->height = 1 + computeHeight(n->left);
    }
    else {
      n->height = 1 + computeHeight(n->right);
    }
  }
}

我认为我收到错误是因为它不喜欢 void 函数中的“+”等运算符。请指教！

Answer 1

我假设您不允许更改函数 return 类型（即使它强制执行了一个相当奇怪的实现）

您不能将 1 添加到 computeHeight 的结果，因为后者 return 什么都没有。

但是，computeHeight 做了一些事情。它有所谓的副作用。这个效果是“在 computeHeight(n) 完成后，n->height 将被设置为给定节点的高度值（从叶子开始）”。你可以使用它：

else if (n->left && !n->right){
    computeHeight(n->left);
    n->height = 1 + n->left->height;
}

在最后一种情况下，你需要先computeHeight两个子树然后比较副作用：

else {
  computeHeight(n->left);
  computeHeight(n->right);
  n->height = 1 + std::max(n->left->height, n->right->height); //slightly refactored ;)
}

Answer 2

您的代码既可以固定也可以简化如下（未经测试）：

void computeHeight(Node *n) {
  if (!n)
    return;

  computeHeight(n->left);
  computeHeight(n->right);

  auto left_height = n->left ? n->left->height : 0;
  auto right_height = n->right ? n->right->height : 0;

  n->height = std::max(left_height, right_height) + 1;
}

计算二叉树的高度作为void函数

Calculating height of binary tree as a void function

c++

binary-tree