二叉树向上遍历到根节点
时间: 2023-09-16 14:12:01 浏览: 40
二叉树向上遍历到根节点的方法是通过递归实现。具体步骤如下:
1. 判断当前节点是否为根节点,如果是则返回该节点;
2. 如果当前节点不是根节点,则递归遍历该节点的父节点,直到遍历到根节点为止。
代码示例(假设树的节点类为Node):
```
public Node upTraversal(Node node) {
if (node.parent == null) { // 判断是否为根节点
return node;
}
return upTraversal(node.parent); // 递归遍历父节点
}
```
注意:这里假设节点类中有parent属性指向父节点。如果节点类中没有parent属性,则需要额外处理,例如在节点类中添加一个方法来获取父节点。
相关问题
用栈如何实现二叉树从指定节点到根节点的路径
使用栈可以很方便地实现从指定节点到根节点的路径,具体实现步骤如下:
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` 开始,循环向上遍历,将遍历到的节点入栈,直到遍历到根节点为止。最后,将栈中的节点依次弹出,即可得到从指定节点到根节点的路径。
二叉树的层次遍历 II
二叉树的层次遍历 II指的是从底向上按层遍历二叉树,并将每一层的节点值存储在一个二维数组中。可以使用队列来实现层次遍历,具体步骤如下:
1. 初始化一个队列,并将根节点加入队列。
2. 通过循环遍历队列中的节点,依次将节点的值存储在一个临时数组中,并将节点的左右孩子节点加入队列。
3. 将临时数组加入结果数组的头部,即每次都插入到结果数组的最前面,实现从底向上的遍历。
4. 重复步骤2和步骤3,直到队列为空。
5. 返回结果数组,即为二叉树的自底向上的层次遍历结果。
下面是使用C++实现的代码示例:
```
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> res;
if (!root) return res;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
vector<int> level;
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode* node = q.front();
q.pop();
level.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
res.insert(res.begin(), level);
}
return res;
}
};
```
以上代码首先将根节点加入队列,然后通过循环遍历队列中的节点,将每一层的节点值添加到临时数组中,并将其左右孩子节点入队。然后将临时数组插入到结果数组的最前面,最后返回结果数组即可。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *2* [C++Leedcode107:二叉树的层次遍历II](https://blog.csdn.net/weixin_43434305/article/details/87711943)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v92^chatsearchT0_1"}}] [.reference_item style="max-width: 50%"]
- *3* [二叉树的层次遍历 II](https://blog.csdn.net/weixin_38853761/article/details/107498308)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v92^chatsearchT0_1"}}] [.reference_item style="max-width: 50%"]
[ .reference_list ]