使用C++将二叉树中的每个节点替换为其中序前驱和后继的和

给定一棵二叉树，我们需要将所有元素替换为其中序前驱和后继的和。中序遍历是图中一条遍历路径，其读取顺序为左节点 – 根节点 – 右节点。该方法将左节点和右节点的元素相加，并用所得的和替换该值。

假设我们有一棵具有以下结构和字符的树：


我们可以找到并存储树的中序遍历结果到一个数组中。之后，我们可以再次进行中序遍历，但这次我们将用数组中的索引替换元素。

让我们来看一些输入场景：

假设输入为二叉树节点读取值：[3 8 15 7 10 3 6 4 9]，则得到的结果二叉树为：

Input: [3 8 15 7 10 3 6 4 9]
Result—
Before: 3 8 15 7 10 3 6 4 9
After: 8 18 15 25 10 16 7 15 4

假设另一个输入为二叉树节点读取值：[4 6 7 8 5 3 2 7 1]，则得到的结果二叉树为：

Input: [4 6 7 8 5 3 2 7 1]
Result—
Before: 8 6 2 5 7 4 7 1 3
After: 6 10 11 9 9 14 5 10 1

示例

以下是上述方法的C++实现：

#include <iostream>
#include <vector>
using namespace std;
class Node {
   public:
   int value;
   Node *left, *right;
   Node(int value) {
      this->value = value;
      left = right = NULL;
   }
};
void solve(Node* root, vector<int>& arr, int& index) {
   if(root == NULL) return;
   solve(root->left, arr, index);
   index++;
   root->value = arr[index-1] + arr[index+1];
   solve(root->right, arr, index);
}
void storeInOrder(Node* root, vector<int>& arr) {
   if(root == NULL) return;
   storeInOrder(root->left, arr);
   arr.push_back(root->value);
   storeInOrder(root->right, arr);
}
void printInorder(Node* root) {
   if(root == NULL) return;
   printInorder(root->left);
   cout << root->value << " ";
   printInorder(root->right);
}
int main() {
   Node* root = new Node(2);
   root->left = new Node(7);
   root->right = new Node(5);
   root->left->left = new Node(2);
   root->left->right = new Node(6);
   root->right->right = new Node(9);
   root->left->right->left = new Node(5);
   root->left->right->right = new Node(11);
   root->right->right->left = new Node(4);
   cout << "Before: ";
   printInorder(root);
   cout << "\n";
   vector<int> arr;
   arr.push_back(0);
   storeInOrder(root, arr);
   arr.push_back(0);
   int index = 0;
   solve(root, arr, index);
   cout << "After: ";
   printInorder(root);
   return 0;
}

输出

Before: 2 7 5 6 11 2 5 4 9
After: 7 7 13 16 8 16 6 14 4

解释

节点 中序前驱 中序后继 新值
2(根节点) 11 5 16
7(root->left) 2 5 7
5(root->right) 2 4 6
2(root->left->left) 0(不可用) 7 7
6(root->left->right) 5 11 16
9(root->right->right) 4 0(不可用) 4
5(root->left->right->left) 7 6 13
11(root->left->right->right) 6 2 8
4(root->right->right->left) 5 9 14

结论

首先存储中序遍历结果，然后依次查找每个元素的中序遍历结果是关键。我们使用索引作为回溯，找出元素插入数组时的位置，然后计算树的新中序遍历结果。我们遍历树和每个节点一次，因此时间复杂度为O(n)，我们以中序遍历的形式存储每个元素，因此空间复杂度为O(n)。

更新于：2022年8月10日

287 次浏览

开启你的职业生涯

通过完成课程获得认证

开始学习
广告