資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究根據子樹權重的差異列印完整二叉樹每個節點的更新級別
在這個問題中，我們將根據左右子樹的權重差異更新每個子節點的級別。
在這裡，我們將遞迴遍歷每個節點的子樹以獲取左右子樹的權重。之後，我們將再次遍歷每個子樹節點，根據左右子樹權重的差異更新其級別。
問題陳述
我們給定一個包含 N 個級別和 2N -1 個節點的完整二叉樹。級別從 0 到 N − 1 按降序排列（0、-1、-2、-3 等）。我們需要根據左右子樹權重的差異更新每個節點的所有子節點的級別。這裡，子樹的權重是所有節點值的總和。
將較輕子樹的每個節點的級別增加權重差。
將較重子樹的每個節點的級別減少權重差。
示例
輸入
N = 2 1 / \ 2 3
輸出
0, 0, -2
解釋
每個節點的初始級別為 [0, -1, -1]。
根節點的級別保持不變。
節點 '1' 的左子樹權重為 2，右子樹權重為 3。因此，權重差為 1。
當我們將較輕子樹的每個節點的級別增加 1 時，節點 2 的級別從 -1 變為 0。
當我們將較重子樹的每個節點的級別減少 1 時，節點 3 的級別從 -1 變為 -2。
輸入
N = 3
1
/ \
2 3
/ \ / \
4 5 6 7
輸出
0, 4, -6, 4, 2, -6, -8
解釋
每個節點的初始級別為 [0, -1, -1, -2, -2, -2, -2]。
對於節點 1，左子樹的權重為 11，右子樹的權重為 16。因此，我們將每個左子樹節點的級別增加 5，並將每個右子樹節點的級別減少 5。
更新後的級別為 [0, 4, -6, 3, 3, -7, -7]。
對於節點 2，權重差為 1。因此，我們需要更新節點 4 和 5 的級別。
對於節點 3，權重差為 1。因此，我們需要更新節點 6 和 7 的級別。
最終級別為 [0, 4, -6, 4, 2, -6, -8]。
方法
在這種方法中，我們將獲取二叉樹每個節點的左右子樹的權重。之後，我們將根據樹是較輕還是較重，根據權重差更新每個子樹節點的級別。因為我們有一個完整的二叉樹，所以左樹總是較輕的，右樹總是較重的。
演算法
步驟 1 − 定義權重陣列並插入二叉樹的初始權重。此外，將每個節點的初始級別插入 levels[] 陣列中。
步驟 2 − 呼叫 createCBT() 函式以建立完整的二叉樹。
步驟 2.1 − 在 createCBT() 函式中，遍歷權重陣列並呼叫 insertNode() 函式以插入給定權重的節點。
步驟 2.1.1 − 在 insertNode() 函式中，建立一個新的 TreeNode。
步驟 2.1.2 − 如果頭節點為空，則將新節點分配給頭節點。否則，如果佇列前端節點的左孩子為空，則插入一個新節點作為左孩子。否則，插入一個新節點作為右孩子，並將前端節點從佇列中彈出。
步驟 2.1.3 − 將 newNode 插入佇列並返回頭節點。
步驟 2.2 − 在每次迭代中更新頭節點，並在函式結束時返回它。
步驟 3 − 現在，執行 calcualteLevel() 函式以計算級別。
步驟 3.1 − 如果二叉樹為空，則從函式返回。
步驟 3.2 − 執行 getWeight() 函式以獲取左右子樹的權重。
步驟 3.2.1 − 在 getWeight() 函式中，將當前節點的權重與左子樹和右子樹的權重相加，並從函式返回它。
步驟 3.3 − 獲取權重差。
步驟 3.4 − 呼叫 updateLevels() 函式以使用權重差更新每個子樹節點。
步驟 3.4.1 − 在 updateLevels() 函式中，將權重差新增到當前節點的值，並對左子樹和右子樹進行遞迴呼叫。
步驟 3.5 − 對左子樹和右子樹進行 calculateLevels() 函式的遞迴呼叫。
步驟 4 − 執行 printLevels() 函式以列印所有節點的級別。在 printLevels() 函式中，我們遞迴遍歷完整的二叉樹並列印每個節點的更新級別。
示例
#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
// To store weight and level
int weight;
int level;
// Left and right pointer
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int wei, int level) {
this->weight = wei;
this->level = level;
left = right = NULL;
}
};
// For inserting a node into a tree
struct TreeNode *insertNode(struct TreeNode *head, int weight, int level, queue<TreeNode *> &que) {
struct TreeNode *new_node = new TreeNode(weight, level);
if (head == NULL)
head = new_node;
// If the left node is empty, insert a new node as a left child
else if (que.front()->left == NULL) {
que.front()->left = new_node;
} else {
// Insert new node as a right child
que.front()->right = new_node;
que.pop();
}
// Insert node into the queue
que.push(new_node);
return head;
}
struct TreeNode *createCBT(vector<int> wei, vector<int> lev) {
struct TreeNode *head = NULL;
// initialize a queue of nodes
queue<TreeNode *> que;
int len = wei.size();
for (int p = 0; p < len; p++) {
// Insert node into the tree
head = insertNode(head, wei[p], lev[p], que);
}
return head;
}
int getWeight(struct TreeNode *head) {
// Weight is 0 for the head node
if (head == NULL)
return 0;
return head->weight + getWeight(head->left) + getWeight(head->right);
}
void updateLevels(struct TreeNode *head, int m) {
if (head == NULL)
return;
// Change the level of the current node
head->level = head->level + m;
// Update the level of each node of the subtree
updateLevels(head->left, m);
updateLevels(head->right, m);
}
void calcualteLevel(struct TreeNode *head) {
if (head == NULL)
return;
int leftWeight = getWeight(head->left);
int rightWeight = getWeight(head->right);
// Get weight difference
int weightDiff = leftWeight - rightWeight;
// Update the levels
updateLevels(head->left, -weightDiff);
updateLevels(head->right, weightDiff);
// Recursive call for subtrees
calcualteLevel(head->left);
calcualteLevel(head->right);
}
void PrintLevels(struct TreeNode *head) {
if (head == NULL)
return;
queue<TreeNode *> que;
que.push(head);
while (!que.empty()) {
cout << que.front()->level << " ";
if (que.front()->left != NULL)
que.push(que.front()->left);
if (que.front()->right != NULL)
que.push(que.front()->right);
que.pop();
}
cout << endl;
}
// Driver code
int main() {
// Number of levels
int N = 3;
int nodes = pow(2, N) - 1;
// Defining the weight of each node
vector<int> weights;
for (int p = 1; p <= nodes; p++) {
weights.push_back(p);
}
vector<int> levels;
// Defining the level of each node
for (int p = 0; p < N; p++) {
for (int q = 0; q < pow(2, p); q++) {
// value of level becomes negative
// While going down the head
levels.push_back(-1 * p);
}
}
// Create a complete binary tree
struct TreeNode *head = createCBT(weights, levels);
calcualteLevel(head);
PrintLevels(head);
return 0;
}
輸出
0 4 -6 4 2 -6 -8
時間複雜度 − O(N)
空間複雜度 − O(N)
56 次檢視
