【算法】二叉树输出根节点到x的路径

分析（递归）：

1. 空树，则查找失败，返回 false
2. 当前结点为所要查找的值，输出结果，返回 true
3. 以上条件不满足，则向左找或向右找，找着了说明当前结点是根到x路径上的点，输出并返回 true
4. 左右都找不到，查找失败，无此结点，返回 false

bool printPath(node* root, int x) {
    if (root == NULL) return false;
    if (root->data == x) {
        printf("%d ", x);
        return true;
    }
    if (printPath(root->left, x) || printPath(root->right, x)) {
        printf("%d ", root->data);
        return true;
    }
    return false;
}

完整实现：

#include <bits/stdc++.h>
using namespace std;
struct node {
    int data;
    node *left, *right;
    node(int x) : data(x) { left = right = NULL; }
};
int pre[] = {1, 4, 3, 5, 8, 9, 2, 6, 7}, in[] = {3, 4, 8, 5, 9, 1, 6, 2, 7};
node* create(int prel, int prer, int inl, int inr) {
    if (prel > prer) return NULL;
    node* root = new node(pre[prel]);
    int k = inl;
    while (in[k] != pre[prel]) k++;
    int numleft = k - inl;
    root->left = create(prel + 1, prel + numleft, inl, k - 1);
    root->right = create(prel + numleft + 1, prer, k + 1, inr);
    return root;
}
// 输出从根节点到x的路径
bool printPath(node* root, int x) {
    if (root == NULL) return false;
    if (root->data == x) {
        printf("%d ", x);
        return true;
    }
    if (printPath(root->left, x) || printPath(root->right, x)) {
        printf("%d ", root->data);
        return true;
    }
    return false;
}
int main() {
    int n = 9;
    // for (int i = 0; i < n; i++) scanf("%d", pre + i);
    // for (int i = 0; i < n; i++) scanf("%d", in + i);
    node* root = create(0, n - 1, 0, n - 1);
    printPath(root, 8);
    return 0;
}

输出结果：

8 5 4 1