c++编写程序,输入一个节点的值,完成在该树中搜索该节点,并输出其路径代码
时间: 2024-03-24 19:37:19 浏览: 22
好的,给出在二叉树中搜索节点并输出路径的代码如下:
```c++
#include<iostream>
#include<vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
vector<int> findPath(TreeNode* root, int target) {
vector<int> path;
if (!root) return path;
find(root, target, path);
return path;
}
bool find(TreeNode* node, int target, vector<int>& path) {
if (!node) return false;
path.push_back(node->val);
if (node->val == target) return true;
if (find(node->left, target, path) || find(node->right, target, path)) return true;
path.pop_back();
return false;
}
};
```
这个程序使用了递归的方法,在二叉树中搜索节点并输出路径。我们先判断当前节点是否为空,如果为空则返回空的路径。然后,我们将当前节点的值加入路径中,如果当前节点的值等于目标值,则返回true。否则,我们递归地搜索当前节点的左子树和右子树,如果左子树或右子树中存在目标值,则返回true。如果左子树和右子树都不存在目标值,则将当前节点从路径中弹出,返回false。
当我们找到目标节点后,路径中存储的就是从根节点到目标节点的路径。因此,我们可以直接返回路径,以便进行后续的处理。