使用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 次瀏覽

開啟你的職業生涯

透過完成課程獲得認證

開始學習
廣告