ToB企服应用市场:ToB评测及商务社交产业平台
标题:
给定二叉树和此中恣意一个节点,找到在中序遍历中的下一个节点
[打印本页]
作者:
傲渊山岳
时间:
2024-7-26 12:36
标题:
给定二叉树和此中恣意一个节点,找到在中序遍历中的下一个节点
在给定二叉树和此中一个节点的情况下,假如每个节点除了有指向左右子节点的指针,还有指向父节点的指针,我们可以很方便地找到在中序遍历中的下一个节点。
#include <iostream>
// 定义二叉树节点结构
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode *parent; // 指向父节点的指针
TreeNode(int x) : val(x), left(nullptr), right(nullptr), parent(nullptr) {}
};
class Solution {
public:
// 获取给定节点在中序遍历中的下一个节点
TreeNode* getNext(TreeNode* node) {
if (node == nullptr) return nullptr;
// 如果当前节点有右子树,返回右子树中最左边的节点
if (node->right != nullptr) {
TreeNode* curr = node->right;
while (curr->left != nullptr) {
curr = curr->left;
}
return curr;
} else {
// 当前节点没有右子树,向上查找
TreeNode* curr = node;
TreeNode* parent = node->parent;
while (parent != nullptr && curr == parent->right) {
curr = parent;
parent = parent->parent;
}
return parent; // 如果 parent 为空,说明当前节点是最后一个节点
}
}
};
// 用于测试:中序遍历打印二叉树
void inorderTraversal(TreeNode* root) {
if (root == nullptr) return;
inorderTraversal(root->left);
std::cout << root->val << " ";
inorderTraversal(root->right);
}
int main() {
// 创建节点
TreeNode* node1 = new TreeNode(1);
TreeNode* node2 = new TreeNode(2);
TreeNode* node3 = new TreeNode(3);
TreeNode* node4 = new TreeNode(4);
TreeNode* node5 = new TreeNode(5);
// 构建树
node2->left = node1;
node1->parent = node2;
node2->right = node3;
node3->parent = node2;
node3->right = node4;
node4->parent = node3;
node4->right = node5;
node5->parent = node4;
Solution solution;
// 测试找到下一个节点的功能
TreeNode* nextNode = solution.getNext(node3);
if (nextNode != nullptr) {
std::cout << "节点 " << node3->val << " 的中序遍历下一个节点是: " << nextNode->val << std::endl;
} else {
std::cout << "节点 " << node3->val << " 是中序遍历的最后一个节点。" << std::endl;
}
return 0;
}
复制代码
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。
欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)
Powered by Discuz! X3.4