（C语言二叉树求指定结点路径）还能减少进出结果栈s的次数吗？

Question

递归求指定结点node在以root为根结点的二叉树中的路径，并保存在栈s中。

#include <stdio.h>
#include <stdlib.h>
#define Stack_Size 50

typedef BiTNode* ElemType;
typedef struct{
    ElemType elem[Stack_Size];
    int top;
}Stack;

void init_stack(Stack *S); // 初始化栈
bool push(Stack* S, ElemType x); //x 入栈
bool pop(Stack* S, ElemType *px); //出栈，元素保存到px所指的单元，函数返回true,栈为空时返回 false
bool top(Stack* S, ElemType *px); //获取栈顶元素，将其保存到px所指的单元，函数返回true，栈满时返回 false
bool is_empty(Stack* S);  // 栈为空时返回 true，否则返回 false



typedef int DataType;

typedef struct Node{
    DataType data;
    struct Node* left;
    struct Node* right;
}BiTNode, *BiTree;



bool path(BiTNode* root, BiTNode* node, Stack* s)
{
    if (root == NULL) {
        return false;
    }
    push(s, root);
    if (root == node) {
        return true;
    }
    BiTNode* bin;
    if (path(root->left, node, s)) {
        return true;
    }
    if (path(root->right, node, s)) {
        return true;
    }
    pop(s, &bin);
    return false;
}

Answer 1

这个代码已经是递归搜索树并把路径存储在栈中的标准方法了。它首先把当前节点压入栈中，然后递归地搜索左子树和右子树。如果在左子树或右子树中找到了目标节点，就直接返回 true。如果左右子树都没有找到，就把当前节点从栈中弹出，然后返回 false。

为了减少入栈和出栈的次数，可以尝试只在找到目标节点时才把路径节点压入栈中。但是，这需要一种不同的搜索策略，可能需要额外的数据结构来记录节点的父节点或者路径信息，可能会使代码变得更复杂，且可能无法有效减少时间复杂度。

所以，如果没有特殊的性能要求，建议保留现有的实现，因为它简单，清晰，容易理解。如果你需要进行性能优化，建议从其他可能的性能瓶颈入手，比如看看是否有更有效的搜索策略，或者是否有更好的数据结构可以使用等等。

至于你的代码中，path函数中递归调用的顺序是先调用左子树，然后调用右子树。如果你知道目标节点更可能在右子树，那么你可以先调用右子树来提高效率。但是，如果你对目标节点在哪边没有任何额外信息，那么保持现有的顺序就可以了，因为在平均情况下，左右子树应该是均匀分布的。