資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學判斷給定二叉樹的垂直層是否已排序 (C++)
概念
針對給定的二叉樹，我們的任務是確定給定垂直層是否已排序。
（在這種情況下，當兩個節點重疊時，請驗證它們在其所在的層中是否形成排序序列。）
輸入
2 / \ 3 6 / \ 8 5 / 7 Level l = -1
輸出
Yes
-1 層的節點是 3 -> 7，它們形成一個排序序列。
輸入
2 / \ 3 7 \ / 4 5 Level l = 0
輸出
Yes
需要注意的是，值為 4 和 5 的節點在二叉樹中重疊。
現在我們驗證這是否按層形成排序序列。0 層的節點是 2 -> 4 -> 5，它們形成一個排序序列。
方法
根據簡單的解決方案，首先我們執行二叉樹的層序遍歷，並將每個垂直層儲存在不同的陣列中。在這種情況下，我們驗證與層 l 對應的陣列是否已排序。需要注意的是，此解決方案的記憶體需求很大，可以減少。
根據高效的解決方案，我們執行二叉樹的垂直層序遍歷，並跟蹤二叉樹垂直層 l 中的節點值。如果前一個元素小於或等於當前元素，則會生成排序序列。在執行垂直層序遍歷時，儲存前一個值並將垂直層 l 中的當前節點與此層 l 的前一個值進行比較。可以看出，如果當前節點值大於或等於前一個值，則必須重複相同的過程，直到層 l 結束。可以看出，如果在任何階段當前節點值小於前一個值，則層 l 未排序。再次觀察到，如果我們到達層 l 的末尾，則該層已排序。
示例
// CPP program to determine whether
// vertical level l of binary tree
// is sorted or not.
#include <bits/stdc++.h>
using namespace std;
// Shows structure of a tree node.
struct Node1 {
int key1;
Node1 *left1, *right1;
};
// Shows function to create new tree node.
Node1* newNode(int key1){
Node1* temp1 = new Node1;
temp1->key1 = key1;
temp1->left1 = temp1->right1 = NULL;
return temp1;
}
// Indicates helper function to determine if
// vertical level l of given binary
// tree is sorted or not.
bool isSorted1(Node1* root1, int level1){
// So If root is null, then the answer is an
// empty subset and an empty subset is
// always considered to be sorted.
if (root1 == NULL)
return true;
// Indicates variable to store previous
// value in vertical level l.
int prevVal1 = INT_MIN;
// Indicates variable to store current level
// while traversing tree vertically.
int currLevel1;
// Indicates variable to store current node
// while traversing tree vertically.
Node1* currNode1;
// Used to declare queue to do vertical order
// traversal. A pair is used as element
// of queue. The first element in pair
// represents the node and the second
// element represents vertical level
// of that node.
queue<pair<Node1*, int>> q1;
// Used to insert root in queue. Vertical level
// of root is 0.
q1.push(make_pair(root1, 0));
// Perform vertical order traversal until
// all the nodes are not visited.
while (!q1.empty()) {
currNode1 = q1.front().first;
currLevel1 = q1.front().second;
q1.pop();
// Verify if level of node extracted from
// queue is required level or not. If it
// is the required level then verify if
// previous value in that level is less
// than or equal to value of node.
if (currLevel1 == level1) {
if (prevVal1 <= currNode1->key1)
prevVal1 = currNode1->key1;
else
return false;
}
// So if left child is not NULL then push it
// in queue with level reduced by 1.
if (currNode1->left1)
q1.push(make_pair(currNode1->left1, currLevel1 - 1));
// So if right child is not NULL then push it
// in queue with level increased by 1.
if (currNode1->right1)
q1.push(make_pair(currNode1->right1, currLevel1 + 1));
}
// So if the level asked is not present in the
// given binary tree, that means that level
// will contain an empty subset. Therefore answer
// will be true.
return true;
}
// Driver program
int main(){
/*
2
/ \
3 6
/ \
8 5
/
7
*/
Node1* root1 = newNode(2);
root1->left1 = newNode(3);
root1->right1 = newNode(6);
root1->left1->left1 = newNode(8);
root1->left1->right1 = newNode(5);
root1->left1->right1->left1 = newNode(7);
int level1 = -1;
if (isSorted1(root1, level1) == true)
cout << "Yes";
else
cout << "No";
return 0;
}輸出
Yes
更新於：2020年7月24日
70 次瀏覽
廣告