在给定二叉树和此中一个节点的情况下,假如每个节点除了有指向左右子节点的指针,还有指向父节点的指针,我们可以很方便地找到在中序遍历中的下一个节点。
- #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企服之家,中国第一个企服评测及商务社交产业平台。 |