C++を使用してバイナリツリーで最長の葉から葉へのパスを印刷するプログラム

このチュートリアルでは、特定の二分木でリーフノードから別のリーフノードに存在する最長のパスを出力するプログラムについて説明します。

つまり、二分木の直径に現れるすべてのノードを印刷する必要があります。ここで、特定の二分木の直径（または幅）は、あるエンドノードから別のエンドノードへの最長パスにあるノードの数として定義されます。

これを解決するために、高さ関数を使用して二分木の直径を計算します。次に、バイナリツリーの左側と右側の部分で最長のパスを見つけます。次に、最後に直径のノードを印刷するために、左側のノード、ルートノード、右側のノードの順に印刷します。

例

#include <bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   Node *left, *right;
};
struct Node* create_node(int data){
   struct Node* node = new Node;
   node->data = data;
   node->left = node->right = NULL;
   return (node);
}
int tree_height(Node* root, int& ans, Node*(&k), int& lh, int& rh, int& f){
   if (root == NULL)
      return 0;
   int left_tree_height = tree_height(root->left, ans, k, lh, rh, f);
   int right_tree_height = tree_height(root->right, ans, k, lh, rh, f);
   if (ans < 1 + left_tree_height + right_tree_height){
      ans = 1 + left_tree_height + right_tree_height;
      k = root;
      lh = left_tree_height;
      rh = right_tree_height;
   }
   return 1 + max(left_tree_height, right_tree_height);
}
void print_roottonode(int ints[], int len, int f){
   int i;
   if (f == 0){
      for (i = len - 1; i >= 0; i--) {
         printf("%d ", ints[i]);
      }
   }
   else if (f == 1) {
      for (i = 0; i < len; i++) {
         printf("%d ", ints[i]);
      }
   }
}
void print_pathr(Node* node, int path[], int pathLen, int max, int& f){
   if (node == NULL)
   return;
   path[pathLen] = node->data;
   pathLen++;
   if (node->left == NULL && node->right == NULL) {
      if (pathLen == max && (f == 0 || f == 1)) {
         print_roottonode(path, pathLen, f);
         f = 2;
      }
   }
   else {
      print_pathr(node->left, path, pathLen, max, f);
      print_pathr(node->right, path, pathLen, max, f);
   }
}
void calc_diameter(Node* root){
   if (root == NULL)
      return;
   int ans = INT_MIN, lh = 0, rh = 0;
   int f = 0;
   Node* k;
   int tree_height_of_tree = tree_height(root, ans, k, lh, rh, f);
   int lPath[100], pathlen = 0;
   print_pathr(k->left, lPath, pathlen, lh, f);
   printf("%d ", k->data);
   int rPath[100];
   f = 1;
   print_pathr(k->right, rPath, pathlen, rh, f);
}
int main(){
   struct Node* root = create_node(12);
   root->left = create_node(22);
   root->right = create_node(33);
   root->left->left = create_node(45);
   root->left->right = create_node(57);
   root->left->right->left = create_node(26);
   root->left->right->right = create_node(76);
   root->left->left->right = create_node(84);
   root->left->left->right->left = create_node(97);
   calc_diameter(root);
   return 0;
}

出力

97 84 45 22 57 26