时间戳

首页 > 解决方案 > 在 C++ 中找到二叉树中的最大高度路径

c++ - 在 C++ 中找到二叉树中的最大高度路径

问题描述

我需要从用户那里获取输入来填充树，然后找到最大高度和获取它的方向。（L - 左和 R - 右）例如，用户输入：50 25 75 15 40 60 30 55 56 57 输出应该是 HRLLRR 但我有 HRRRR

或者输入的另一个例子：50 25 75 15 40 60 100 输出必须是 HRR 但我有 HRRR

#include <iostream> 
#include <string>
#include <cstring>
#include <cstdlib>
#include <queue>

using namespace std;

template <typename T>
class Tree {
private : 
    T info;
    Tree* left;
    Tree* right;
public : 
    Tree() {
        info = NULL;
        left = right = NULL;
    }
    Tree* insert(Tree<T>* head,T value);
    void InOrder(Tree* head);
    void findMaxPath(Tree<T>*);
    int findMax(Tree<T>*);
};

    string path="H";

int main() {
    Tree<int>* head = NULL; 
    char ch;
    int info; 
    do  {
        cin >> ch;
        switch (ch) {
        case 'i':
            cin >> info;
            head = head->insert(head, info);
            break;
        case 'p':
            head->InOrder(head);
            cout << endl;
            break;
        case 'm': 
            head->findMaxPath(head);
            cout << path << endl;
            break;
        }
    }while (ch != 'e');
}

template <typename T>
Tree<T>* Tree<T>::insert(Tree<T>* head,T value) {
    if (head == NULL) {
        head = new Tree<T>();
        head->info = value;
        return head;
    }
    if (head->info > value) {
        head->left = insert(head->left, value);
    }
    else
        head->right = insert(head->right, value);

    return head;
}
template <typename T>
void Tree<T>::InOrder(Tree<T>* head) {
    if (head != NULL) {
        InOrder(head->left);
        cout << head->info << " ";
        InOrder(head->right);
    }
}
template <typename T>
void Tree<T>::findMaxPath(Tree<T>* head){
    if (head == NULL) {
        cout << "Empty" << endl;
        return;
    }
    else findMax(head);
}
template <typename T>
int Tree<T>::findMax(Tree<T>* head){
    if (head==NULL){
        cout << path << endl;
        return 0;
    }
    else{  
        int leftMax, rightMax; 
        int max = head->info;  
        if(head->left != NULL){  
            leftMax = findMax(head->left);  
            if(leftMax > max){
            max = leftMax;  
            path+="L";
            }
        }  
        if(head->right != NULL){  
          rightMax = findMax(head->right);
          if(rightMax > max){
            max = rightMax;  
            path+="R";
            }
        }  
    return max;  
    }  
}

标签： c++tree

解决方案

假设：您将给定的节点序列一个一个地插入到二叉搜索树中。

问题出在你的findMax()功能上。path请注意，即使您没有遍历“最大”区域，也将“L”或“R”附加到变量中。

对于第二个输入（50 25 75 15 40 60 100），追加按以下顺序完成：25（40），75（100），50（75）。因此，当您对根的左子树进行递归（乘以 25）时，您会得到一个额外的“R”。

此外，您将max变量设置为节点的值，并且您正在获取更大的值子节点，而不是问题中所述的最大高度子节点。

推荐阅读