c++ - 通过二叉树选择所需的路径

Question

我已经在这里问了一个问题。我得到了答案。实际上，这是一种不同的路径，即每个级别我有两个选项，向上（1）或向下（-1），我有n级别。因此我有2^n路径。

现在在这个当前问题中，我想选择一些所需的路径。我想要的路径有以下两个条件。

1. 给定路径的终点，比如说，1。因此，我想选择那些最终到达的路径，1即给定路径与nlevel 的总和为1。

2. 我想将这些路径绑定在 #1 之间，比如说，9和-9. 例如，我想避免顺序的 9up 或9down 的总和，即大于9和小于-9。

这是我的尝试：

int popcount(unsigned x){
    int c = 0;
    for (; x != 0; x >>= 1)
        if (x & 1)
            c++;
    return c;
}
void selected_path(vector<int> &d, int n){
    d.clear();
    int size = 1<<n;
    d.resize(size);
    for (int i = 0; i  < size; ++i) {
            d[i] = n-2.0*popcount(i);
    }
}

在上面的代码中，d[]给了我所有可能的路径，即2^n. 但我想选择具有上述两个条件的路径。

编辑：答案但效率不高！

#include <iostream> 
#include <vector> 
#include <algorithm>
using namespace std; 

struct node{ 
    int data; 
    node *left, *right; 
}; 

struct node *create(int x, int n, int limit){
    struct node *newnode;
    newnode = new node();
    n++;
    if(n==(limit+2)) return 0;
    newnode->data = x;
    x =  newnode->data + 1;
    newnode->left = create(x,n,limit);
    x =  newnode->data -1 ;
    newnode->right = create(x, n,limit);
    return newnode;
}

void inorder(std::vector<int> &d, node *root, vector<int> &stack, int uplimit, int downlimit){ //uplimit,downlimit
    if(root == NULL) return;
    stack.push_back(root->data);
    
    inorder(d,root->left,stack,uplimit,downlimit);
    if(root->left == 0 and root->right ==0){
        if(stack[stack.size() -1] == 1){
            int max=*max_element(stack.begin(), stack.end());
            int min=*min_element(stack.begin(), stack.end());
            if(max < uplimit and min > downlimit){
                for(int i = 1; i < stack.size(); i++){
                    d.push_back(stack[i]);
                }
            }
        }
    }
    inorder(d,root->right,stack,uplimit,downlimit);
    stack.pop_back(); 
}
int main(){
    
    int limit = 7;
    struct node *root;
    root = create(0,0,limit);

    std::vector<int> stack;
    std::vector<int>  d;
    int uplimit = 9;
    int downlimit = -9;
    
    inorder(d,root, stack,uplimit,downlimit);
    stack.clear();
    int n_path = int(d.size()/(limit));
    for(int ip =0; ip < n_path; ip++){
        for(int i = 1; i <=limit; i++){
            cout << d[ip*(limit)+(i-1)] << "\t";
        }
        cout << endl;
    }
}

一个可能的答案可以是上面的代码。这d[]是一个二维数组，第一维是路径的数量，第二维是路径中节点的值。

但问题是它在内存（如果limit > 20）方面效率不高，因为它root-> data保存了所有可能的节点，这是不必要的。

如果有人能提出一些想法来提高效率，我将不胜感激

标签： c++cfor-loopbinary-treebinary-search-tree