用栈如何实现二叉树从指定节点到根节点的路径
时间: 2023-06-27 13:06:11 浏览: 49
使用栈可以很方便地实现从指定节点到根节点的路径,具体实现步骤如下:
1. 定义一个栈,用于存储路径上的节点。
2. 从指定节点开始,将其入栈。
3. 循环执行以下步骤,直到当前节点为根节点:
- 将当前节点入栈。
- 将当前节点的父节点设置为当前节点,并将其作为下一次循环的当前节点。
4. 循环结束后,栈中存储的就是从指定节点到根节点的路径上的所有节点。
具体的实现代码如下(假设二叉树的节点定义为如下结构体):
```c++
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
```
```c++
vector<TreeNode*> getPath(TreeNode* root, TreeNode* target) {
vector<TreeNode*> path;
stack<TreeNode*> st;
TreeNode* cur = target;
while (cur || !st.empty()) {
if (cur) {
st.push(cur);
cur = cur->parent;
} else {
cur = st.top();
st.pop();
path.push_back(cur);
cur = cur->parent;
}
}
return path;
}
```
在上面的代码中,我们从指定节点 `target` 开始,循环向上遍历,将遍历到的节点入栈,直到遍历到根节点为止。最后,将栈中的节点依次弹出,即可得到从指定节点到根节点的路径。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)