c++ - 实现递归 Void 函数（查找二叉搜索树的高度）

Question

我需要实现一个 void 函数来计算二叉树中每个节点的高度并将其存储在每个节点中。我在网上找到了一些本质上是递归的解决方案，但它们返回 int。示例包括（https://www.geeksforgeeks.org/write-ac-program-to-find-the-maximum-depth-or-height-of-a-tree/）。模型答案之间的区别，除了它不是一个空函数外，它也不存储每个节点的高度。

这是我对解决方案的尝试，但我似乎无法让代码工作，也无法重新调整模型答案以递归地应用于 void 函数。当我在帮助程序代码中运行我的代码进行测试时，它甚至没有显示任何输出。

void computeHeight(Node *n) {
  Node* ltraverser = n;
  Node* rtraverser = n;
  int lheight = 0;
  int rheight =0;

  if (n == NULL) {
   n->height = 0;
  }

  while (ltraverser->left != NULL) {
   ltraverser = ltraverser->left;
   lheight += 1;
  }

  while (rtraverser->right != NULL) {
   rtraverser = rtraverser->right;
   lheight += 1;
  }

  if (lheight > rheight) {
    n->height = lheight;
  }

  else {
    n->height = rheight;
  }

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

以供参考：

The starter code below defines a class called "Node" that has two child pointers ("left" , "right") and an integer "height" member variable. There is also a constructor Node() that initializes the children to nullptr and the height to -1.

/*
The height of a node is the number of edges in
its longest chain of descendants.

Implement computeHeight to compute the height
of the subtree rooted at the node n. Note that
this function does not return a value. You should
store the calculated height in that node's own
height member variable. Your function should also
do the same for EVERY node in the subtree rooted
at the current node. (This naturally lends itself
to a recursive solution!)

Assume that the following includes have already been
provided. You should not need any other includes
than these.

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>

You have also the following class Node already defined.
You cannot change this class definition, so it is
shown here in a comment for your reference only:

class Node {
public:
  int height; // to be set by computeHeight()
  Node *left, *right;
  Node() { height = -1; left = right = nullptr; }
  ~Node() {
    delete left;
    left = nullptr;
    delete right;
    right = nullptr;
  }
};
*/

用于测试代码

// This function prints the tree in a nested linear format.
void printTree(const Node *n) {
  if (!n) return;
  std::cout << n->height << "(";
  printTree(n->left);
  std::cout << ")(";
  printTree(n->right);
  std::cout << ")";
}

  Node *n = new Node();
  n->left = new Node();
  n->right = new Node();
  n->right->left = new Node();
  n->right->right = new Node();
  n->right->right->right = new Node();

  computeHeight(n);

  printTree(n);
  std::cout << std::endl << std::endl;
  printTreeVertical(n);

  delete n;
  n = nullptr;

  return 0;
}

标签： c++algorithmrecursiondata-structures

Answer 1

不是返回节点高度，而是在左右节点上递归调用 computeHeight，然后将最大高度存储在节点结构中。

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <algorithm>

class Node {
public:
  int height;
  Node *left, *right;
  Node() { height = -1; left = right = nullptr; }
  ~Node() {
    delete left;
    left = nullptr;
    delete right;
    right = nullptr;
  }
};

void computeHeight(Node *node) {

    if (node == nullptr) {
        return;
    }

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

    int leftHeight = -1;
    int rightHeight = -1;

    if (node->left != nullptr) {
        leftHeight = node->left->height;
    }

    if (node->right != nullptr) {
        rightHeight = node->right->height;
    }

    node->height = std::max(leftHeight, rightHeight) + 1;
}

void printNode(Node *n, int level = 0) {
    if (n == nullptr) {
        return;
    }

    std::cout << std::string(level * 2, ' ') << "Height = " << n->height << "\n";

    printNode(n->left,  level + 1);
    printNode(n->right, level + 1);
}


int main() {
  Node *n = new Node();
  n->left = new Node();
  n->right = new Node();
  n->right->left = new Node();
  n->right->right = new Node();
  n->right->right->right = new Node();


  computeHeight(n);
  printNode(n);
}