【二叉排序树算法】 对于二叉排序树 bt，设计一个算法输出在该树中查找某个关键字k所经过的路径，写出其非递归算法要求： 1 给出算法的基本设计思想； 2 根据设计思想，采用程序设计语言描述算法（C或者C++等），关键之处给出注释； 3 程序运行结果示例。

基本设计思想：
首先，在二叉排序树中查找关键字k，如果树为空，则返回空路径，否则从根节点开始遍历，如果当前节点的值等于k，则返回路径，否则判断k与当前节点值的大小关系，如果k大于当前节点值，则继续遍历右子树，否则遍历左子树。遍历时将经过的节点加入路径中，直到找到k或遍历到叶子节点时停止。

非递归算法实现：

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

vector<TreeNode*> findPath(TreeNode* root, int k) {
    vector<TreeNode*> path;  // 存放路径
    TreeNode* cur = root;
    while (cur) {
        path.push_back(cur);  // 将当前节点加入路径
        if (cur->val == k) {
            return path;  // 找到了节点，返回路径
        } else if (cur->val < k) {
            cur = cur->right;  // 继续遍历右子树
        } else {
            cur = cur->left;  // 继续遍历左子树
        }
    }
    path.clear();  // 如果没有找到节点，则清空路径
    return path;
}

程序运行结果示例：
假设二叉排序树如下所示：

        5
       / \
      3   8
     / \   \
    2   4   9

调用findPath(root, 4)会返回路径[5, 3, 4]，调用findPath(root, 7)会返回空路径[]。