给定二叉树和此中恣意一个节点，找到在中序遍历中的下一个节点 ...

在给定二叉树和此中一个节点的情况下，假如每个节点除了有指向左右子节点的指针，还有指向父节点的指针，我们可以很方便地找到在中序遍历中的下一个节点。

1. #include <iostream>
3. // 定义二叉树节点结构
4. struct TreeNode {
5.     int val;
6.     TreeNode *left;
7.     TreeNode *right;
8.     TreeNode *parent; // 指向父节点的指针
9.     TreeNode(int x) : val(x), left(nullptr), right(nullptr), parent(nullptr) {}
10. };
12. class Solution {
13. public:
14.     // 获取给定节点在中序遍历中的下一个节点
15.     TreeNode* getNext(TreeNode* node) {
16.         if (node == nullptr) return nullptr;
18.         // 如果当前节点有右子树，返回右子树中最左边的节点
19.         if (node->right != nullptr) {
20.             TreeNode* curr = node->right;
21.             while (curr->left != nullptr) {
22.                 curr = curr->left;
23.             }
24.             return curr;
25.         } else {
26.             // 当前节点没有右子树，向上查找
27.             TreeNode* curr = node;
28.             TreeNode* parent = node->parent;
29.             while (parent != nullptr && curr == parent->right) {
30.                 curr = parent;
31.                 parent = parent->parent;
32.             }
33.             return parent; // 如果 parent 为空，说明当前节点是最后一个节点
34.         }
35.     }
36. };
38. // 用于测试：中序遍历打印二叉树
39. void inorderTraversal(TreeNode* root) {
40.     if (root == nullptr) return;
41.     inorderTraversal(root->left);
42.     std::cout << root->val << " ";
43.     inorderTraversal(root->right);
44. }
46. int main() {
47.     // 创建节点
48.     TreeNode* node1 = new TreeNode(1);
49.     TreeNode* node2 = new TreeNode(2);
50.     TreeNode* node3 = new TreeNode(3);
51.     TreeNode* node4 = new TreeNode(4);
52.     TreeNode* node5 = new TreeNode(5);
54.     // 构建树
55.     node2->left = node1;
56.     node1->parent = node2;
57.     node2->right = node3;
58.     node3->parent = node2;
59.     node3->right = node4;
60.     node4->parent = node3;
61.     node4->right = node5;
62.     node5->parent = node4;
64.     Solution solution;
66.     // 测试找到下一个节点的功能
67.     TreeNode* nextNode = solution.getNext(node3);
68.     if (nextNode != nullptr) {
69.         std::cout << "节点 " << node3->val << " 的中序遍历下一个节点是： " << nextNode->val << std::endl;
70.     } else {
71.         std::cout << "节点 " << node3->val << " 是中序遍历的最后一个节点。" << std::endl;
72.     }
74.     return 0;
75. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。