二叉搜索樹

題目描述

判斷兩序列是否為同一個二叉搜索樹序列。

輸入描述

第一行是一個數 n ( 1 <= n <= 20 )，表示有 n 個二叉搜索樹序列需要判斷。
接下去一行是一個序列，序列長度小于 10 ，包含 0 ~ 9 的數字，沒有重復數字，根據這個序列可以構造出一棵二叉搜索樹。
接下去的 n 行有 n 個序列，每個序列格式跟第一個序列一樣，請判斷這兩個序列——該行序列和第二行序列是否能組成同一棵二叉搜索樹。

輸出描述

對于最后 n 行的每一行詢問，如果序列相同則輸出 YES，否則輸出 NO。

用例輸入 1

2
567432
543267
576342

用例輸出 1

YES
NO

代碼

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;struct node // 節點
{int val;node *lc, *rc;
};
bool ok;                     // 當前詢問中兩樹是否相同
node *insert(node *p, int x) // 中序序列構建二叉搜索樹
{if (p == NULL) // 當前節點為空{// 創建新節點node *new_node = new node;new_node->val = x;new_node->lc = NULL;new_node->rc = NULL;return new_node;}else // 當前節點不為空{// 二叉搜索樹的遍歷過程，從而找到應該建立新節點的位置if (p->val > x)p->lc = insert(p->lc, x);elsep->rc = insert(p->rc, x);return p;}
}
void check(node *standard_root, node *root)
{if (standard_root != NULL && root != NULL) // 兩棵樹該節點都不為空{// 中序遍歷check(standard_root->lc, root->lc);if (standard_root->val != root->val) // 判斷對應節點值是否相同{ok = false;return; // 若已確定答案，無需繼續遞歸}check(standard_root->rc, root->rc);}else if (standard_root != NULL || root != NULL) // 一棵樹有該節點，另一棵樹沒有對應節點，說明兩樹不相同{ok = false;return; // 若已確定答案，無需繼續遞歸}
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n;string s;cin >> n;node *standard_root = NULL;cin >> s;for (int i = 0; i < s.size(); i++) // 構建標準樹standard_root = insert(standard_root, s[i] - '0');for (int i = 0; i < n; i++) // n個二叉搜索樹，對應n個詢問{ok = true; // 每次詢問都要先初始化為truenode *root = NULL;cin >> s;for (int i = 0; i < s.size(); i++) // 構建詢問樹root = insert(root, s[i] - '0');check(standard_root, root); // 中序遍歷，判斷兩棵樹是否一致if (ok)cout << "YES" << '\n';elsecout << "NO" << '\n';}return 0;
}