1. 二叉樹(shù)創(chuàng)建字符串
相信大部分人看了題目描述之后，都會(huì)和我一樣一臉的懵逼。直到我看到了一個(gè)描述才恍然大悟
分為3種情況：
- 左右都為空 --省略
- 右為空，左不為空 – 省略
- 左為空，右不為空–不省略
這里復(fù)習(xí)一下二叉樹(shù)的前序遍歷、中序遍歷、和后序遍歷
前序的結(jié)果是：ABDEGCF
中序的結(jié)果是：DBGEACF
后序的結(jié)果是：DGEBFCA
class Solution {
public:
string tree2str(TreeNode* root) {
if (root == nullptr)
{
return "";
}
string str = to_string(root->val);
if (root->left || root->right) // 特別注意這個(gè)條件
{
str += "(";
str += tree2str(root->left);
str += ")";
}
if (root->right)
{
str += "(";
str += tree2str(root->right);
str += ")";
}
return str;
}
};
2. 二叉樹(shù)的層序遍歷
思路大致是這樣的：
一個(gè)隊(duì)列，接著一個(gè)levelSize來(lái)記錄每層有幾個(gè)數(shù)據(jù)，如果這個(gè)數(shù)字是0，則表示這層的數(shù)據(jù)出完
出3將9和20帶到隊(duì)列，levelSize為2 。如此循環(huán)下去。
如果這個(gè)隊(duì)列不為空，就一直循環(huán)下去，直到這個(gè)隊(duì)列為空為止。
代碼實(shí)現(xiàn)：
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> q;
int levelSize = 0;
if (root)
{
q.push(root);
levelSize = 1;
}
vector<vector<int>> vv;
while (!q.empty()) // 如果隊(duì)列不為空，就繼續(xù)
{
// 通過(guò)levelSize控制一層一層的出
vector<int> v;
while (levelSize--)
{
TreeNode* front = q.front();
q.pop();
v.push_back(front->val);
if (front->left)
{
q.push(front->left);
}
if (front->right)
{
q.push(front->right);
}
}
vv.push_back(v);
// 更新下一層的個(gè)數(shù)
levelSize = q.size();
}
return vv;
}
};
3. 二叉樹(shù)的層序遍歷Ⅱ
這個(gè)題目與上一題目，差不多，我們只需要將最后的答案逆置即可
4. 二叉樹(shù)的最近公共祖先
思路一：公共祖先的特征，如果一個(gè)在左子樹(shù)，一個(gè)在右子樹(shù)。那么這個(gè)節(jié)點(diǎn)就是公共祖先。
class Solution {
public:
bool isInTree(TreeNode* root, TreeNode* x) {
if (root == nullptr) {
return false;
}
return x == root
|| isInTree(root->left, x)
|| isInTree(root->right, x);
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == nullptr) {
return nullptr;
}
if (p == root || q == root) {
return root;
}
// 判斷p節(jié)點(diǎn)是在root的左邊還是右邊
bool pInLeft = isInTree(root->left, p);
bool pInRight = !pInLeft;
// 判斷q節(jié)點(diǎn)是在root的左邊還是右邊
bool qInLeft = isInTree(root->left, q);
bool qInRight = !qInLeft;
if ((pInLeft && qInRight) || (pInRight && qInLeft)) {
return root;
}
// 如果都在左邊，則轉(zhuǎn)換為在左樹(shù)尋找公共祖先
else if (pInLeft && qInLeft) {
return lowestCommonAncestor(root->left, p, q);
}
else {
return lowestCommonAncestor(root->right, p, q);
}
}
};
思路二：公共祖先的特征，如果一個(gè)在我的左子樹(shù)，一個(gè)在我的右子樹(shù)，我就是公共祖先
如果是搜索二叉樹(shù)可以?xún)?yōu)化到O(N)
- 一個(gè)比根小，一個(gè)比根大，根就是公共祖先
- 都比根小，遞歸左樹(shù)查找
- 都比根大，遞歸右樹(shù)查找
但是這個(gè)題目我們并不是搜索二叉樹(shù)，要求優(yōu)化到O(N)
這里只能使用另外一種思路，將p和q的路徑求出來(lái)，放到容器當(dāng)中，轉(zhuǎn)換為路徑相交問(wèn)題
class Solution {
public:
bool getPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& path) {
if (root == nullptr) {
return false;
}
path.push(root);
if (root == x) {
return true;
}
if (getPath(root->left, x, path)) {
return true;
}
if (getPath(root->right, x, path)) {
return true;
}
path.pop();
return false;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
stack<TreeNode*> pPath, qPath;
getPath(root, p, pPath);
getPath(root, q, qPath);
while (pPath.size() != qPath.size()) {
if (pPath.size() > qPath.size()) {
pPath.pop();
}
else {
qPath.pop();
}
}
while (pPath.top() != qPath.top()) {
pPath.pop();
qPath.pop();
}
return pPath.top();
}
};
上述代碼的關(guān)鍵在于找到每個(gè)節(jié)點(diǎn)的路徑
5. 二叉搜索樹(shù)與雙向鏈表
看到這個(gè)題目我們的第一個(gè)想法可能是把所有的節(jié)點(diǎn)拿出來(lái)，然后尾插到一個(gè)雙向鏈表上，其實(shí)并沒(méi)有這么簡(jiǎn)單，我們能夠想到的出題人當(dāng)然也能夠想到。
這個(gè)題目有以下幾個(gè)要求：
我們需要在原樹(shù)上進(jìn)行操作。
class Solution {
public:
void inorderTraversal(TreeNode* cur, TreeNode*& prev) {
if (cur == nullptr) {
return;
}
inorderTraversal(cur->left, prev);
cur->left = prev;
if (prev) {
prev->right = cur;
}
prev = cur;
inorderTraversal(cur->right, prev);
}
TreeNode* Convert(TreeNode* pRootOfTree) {
TreeNode* prev = nullptr;
inorderTraversal(pRootOfTree, prev);
TreeNode* head = pRootOfTree;
while (head && head->left) {
head = head->left;
}
return head;
}
};
以上的這幅圖是精髓所在
6. 從前序與中序遍歷序列構(gòu)造二叉樹(shù)
class Solution {
public:
TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder, int& previ, int inbegin, int inend) {
if (inbegin > inend) {
return nullptr;
}
TreeNode* root = new TreeNode(preorder[previ]);
// 分割出左右區(qū)間
int rooti = inbegin;
while (rooti <= inend) {
if (inorder[rooti] == preorder[previ]) {
break;
}
else {
rooti++;
}
}
++previ;
// [inbegin, rooti - 1], rooti, [rooti + 1, inend]
root->left = _buildTree(preorder, inorder, previ, inbegin, rooti - 1);
root->right = _buildTree(preorder, inorder, previ, rooti + 1, inend);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int i = 0;
return _buildTree(preorder, inorder, i, 0, inorder.size() - 1);
}
};
7. 二叉樹(shù)的前序遍歷(非遞歸)
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
TreeNode* cur = root;
vector<int> v;
while (cur || !st.empty()) {
// 1. 開(kāi)始訪問(wèn)一棵樹(shù)
// 2. 左路節(jié)點(diǎn)
// 3. 左路節(jié)點(diǎn)的右子樹(shù)
while (cur) {
v.push_back(cur->val);
st.push(cur);
cur = cur->left;
}
// 訪問(wèn)右子樹(shù)
TreeNode* top = st.top();
st.pop();
// 子問(wèn)題訪問(wèn)右子樹(shù)
cur = top->right;// 這個(gè)地方非常重要
}
return v;
}
};
8. 二叉樹(shù)的中序遍歷(非遞歸)
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
TreeNode* cur = root;
vector<int> v;
while (cur || !st.empty()) {
while (cur) {
st.push(cur);
cur = cur->left;
}
// 棧里面取到左路節(jié)點(diǎn)，左路節(jié)點(diǎn)的左子樹(shù)訪問(wèn)完了
TreeNode* top = st.top();
st.pop();
v.push_back(top->val);
cur = top->right;
}
return v;
}
};
8. 二叉樹(shù)的后序遍歷(非遞歸)
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
TreeNode* cur = root;
vector<int> v;
TreeNode* prve = nullptr;
while (cur || !st.empty()) {
while (cur) {
st.push(cur);
cur = cur->left;
}
// 棧里面取到左路節(jié)點(diǎn)，左路節(jié)點(diǎn)的左子樹(shù)訪問(wèn)完了
TreeNode* top = st.top();
// 右為空或者右已經(jīng)訪問(wèn)過(guò)了，可以訪問(wèn)根節(jié)點(diǎn)
if (top->right == nullptr || top->right == prve) {
v.push_back(top->val);
st.pop();
prve = top;
}
else {
cur = top->right;
}
}
return v;
}
};
這里對(duì)非遞歸的三種代碼進(jìn)行對(duì)比：文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-499083.html
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-499083.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】二叉樹(shù)經(jīng)典題目的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
