關于最近
最近在看演算法相關的，接下來想記錄一下自己學習的、個人認為比較值得記錄的演算法，
這篇博客主要是用自己的理解復述了根據中序、前序遍歷重建二叉樹這個博客的內容，大家可以主要看這個博客，我寫得不如遠矣，
根據前序和中序遍歷重建二叉樹
我們知道前序、中序、后序遍歷二叉樹有很多方法，比如遞回進行遍歷，使用堆疊/佇列進行深度/廣度優先遍歷，更有甚者使用Morris方法進行額外空間復雜度為O(1)的遍歷，但從遍歷后的序列重建二叉樹就比較麻煩，
這里描述一下從前序遍歷序列和中序遍歷序列重構二叉樹的方法，要求二叉樹沒有重復的元素，
這里我先給出二叉樹節點的定義：
struct TreeNode {
public:
TreeNode(int val, TreeNode* left = nullptr, TreeNode* right = nullptr)
: val(val), left(left), right(right)
{}
int val;
TreeNode* left;
TreeNode* right;
};
遞回方法
數本身就是遞回定義的，使用遞回的方法來重構二叉樹大概也是最簡單的了吧，
我們先來看一棵樹：
其先序遍歷為：4, 2, 1, 3, 6, 5
中序遍歷為：1, 2, 3, 4, 5, 6
先序遍歷的順序為：根節點（當前節點）-左子樹-右子樹；
中序遍歷的順序為：左子樹-根節點（當前節點）-右子樹；
使用遞回來重構一棵二叉樹，其實就是遞回地重構出某棵樹的左右子樹，那么如何遞回的重構出左右子樹呢？
遞回一定要有終結的狀態，而且要使得可變地引數逐步向終結狀態靠近，否則遞回就會無限的呼叫下去，直到堆疊爆掉，那么在重構程序中如何設定可變的引數，終結的狀態又在哪里呢？
我們觀察上面的先序遍歷和中序遍歷，可以發現在先序遍歷中，一棵子樹上的節點一定是靠在一起的比如4節點的左子樹包括1, 2, 3，這三個節點在先序遍歷和中序遍歷都是靠在一起的，也就是說如果要重構出這棵子樹只需要這個范圍內的數字，范圍不就變窄了嗎，變數是不是就可以設定為先序遍歷和后序遍歷中該子樹中元素的左側下標和右側下表，終結的狀態是不是就可以設定為左右下標相等（意味著沒有左右子樹），或者左下標小于右下標（意味著越界，直接回傳nullptr）？
我們繼續往下看，如果這樣設定引數如何來重構這棵樹呢？我們來觀察先序遍歷，先序遍歷的第一個節點必然是根節點，這樣根節點就確定了，但我們還不知道左子樹是哪些節點，右子樹是哪些節點，因為我們要求二叉樹中不能有重復節點，而我們又知道了當前的根節點，就可以在中序遍歷中找到這個根節點，而中序遍歷又是先遍歷左子樹，再遍歷當前節點（根節點），再遍歷右子樹，那就簡單了，從中序遍歷的最左側到根節點前面都是左子樹的部分，從根節點右側一直到中序遍歷的最右側都是右子樹的部分，這樣我們又可以得到左右子樹各自的數量，就可以確定先序遍歷中左右子樹的范圍了（先序遍歷中從根節點到最右側就分別是左子樹和右子樹），
將上面的分析程序轉化為代碼如下：
class Solution {
public:
TreeNode* rebuildTree(const std::vector<int>preOrder, const std::vector<int>& inOrder) {
assert(preOrder.size() == inOrder.size());
for (long idx = 0; idx < inOrder.size(); ++idx) { // 方便查找根節點在中序遍歷中的下標
inOrderIdx[inOrder[idx]] = idx;
}
return rebuildTree_aux(preOrder, inOrder, 0, preOrder.size()-1, 0, inOrder.size()-1);
}
private:
TreeNode* rebuildTree_aux(const std::vector<int>& preOrder, // 先序遍歷序列
const std::vector<int>& inOrder, // 中序遍歷序列，其實用不到
long preLeftIdx, long preRightIdx, // 重構當前子樹用到的先序遍歷的左右邊界
long inLeftIdx, long inRightIdx) { // 重構當前子樹用到的中序遍歷的左右邊界
assert(preRightIdx - preLeftIdx == inRightIdx - inLeftIdx);
if(preLeftIdx > preRightIdx) // 越界，直接回傳nullptr
return nullptr;
TreeNode* root = new TreeNode(preOrder[preLeftIdx]);
if(preLeftIdx == preRightIdx) // 只有一個節點，不評估左右子樹
return root;
long inRootIdx = inOrderIdx[preOrder[preLeftIdx]]; // 查找根節點在中序遍歷序列中的下標
long leftSize = 0; // 記錄左子樹的大小，用于在先序遍歷序列中確定右子樹的范圍
if(inRootIdx > inLeftIdx) {
// 左邊還有，左邊有左子樹
long leftInLeftIdx = inLeftIdx;
// 中序遍歷，根節點左側的節點就是左子樹最右邊的節點
long leftInRightIdx = inRootIdx - 1;
long leftDif = leftInRightIdx - leftInLeftIdx;
leftSize = leftDif + 1;
// 先序遍歷，最左邊節點（根節點）右邊就是左子樹的最左邊節點
long leftPreLeftIdx = preLeftIdx + 1;
long leftPreRightIdx = leftPreLeftIdx + leftDif;
root->left = rebuildTree_aux(preOrder, inOrder, leftPreLeftIdx, leftPreRightIdx, leftInLeftIdx, leftInRightIdx);
}
if (inRootIdx < inRightIdx) {
// 中序遍歷中，根節點右側還有節點，是屬于右子樹的
long rightInLeftIdx = inRootIdx + 1;
long rightInRightIdx = inRightIdx;
long rightDif = rightInRightIdx - rightInLeftIdx;
long rightPreLeftIdx;
// 下面可以合并，但為了清楚沒有合并
if (leftSize == 0) {
// 如果沒有左子樹，那么先序遍歷根節點后面的節點就是右子樹的最左側
rightPreLeftIdx = preLeftIdx + 1;
} else {
// 如果有左子樹，需要跳過左子樹和根節點
rightPreLeftIdx = preLeftIdx + 1 + leftSize;
}
long rightPreRightIdx = rightPreLeftIdx + rightDif;
root->right = rebuildTree_aux(preOrder, inOrder, rightPreLeftIdx, rightPreRightIdx, rightInLeftIdx, rightInRightIdx);
}
return root;
}
std::unordered_map<long, long> inOrderIdx;
};
迭代方法
和上面一樣，我們先來給出一棵樹：
先序遍歷：1, 2, 3, 4, 5, 6, 7, 8, 9
中序遍歷：4, 3, 2, 5, 1, 7, 6, 8, 9
先序遍歷的順序為：根節點（當前節點）-左子樹-右子樹；
中序遍歷的順序為：左子樹-根節點（當前節點）-右子樹；
在先序遍歷中，遍歷某個子樹時，總是從上到下先遍歷該子樹從根節點開始的左孩子，
什么時候到最左邊呢？我們再看中序遍歷，中序遍歷在遍歷一個子樹的時候總是先遍歷該子樹的最左邊節點，也就是說我們先當先序遍歷到中序遍歷該子樹的中序遍歷的第一個節點時，就到了最左側節點，
后面就是該子節點或者其祖先節點右子樹的部分了，那是哪個節點的右子樹部分呢？我們在看中序遍歷，如果一個節點的右子樹是空的，那么其中序遍歷的后一個節點就是其祖先節點，
也就是說我們在一開始組織遍歷先序節點的時候建立一個堆疊，并有一個變數idx記錄中序遍歷的當前位置并初始化為0，每遍歷一個節點就將其入堆疊stack，當遇到右孩子（即堆疊頂結點stack.top()等于inOrder[idx]）時，就將堆疊頂彈出并記錄，向后移動中序遍歷位置idx，查看堆疊頂結點和當前中序遍歷的節點是否相等，相等就說明剛剛彈出的節點沒有右孩子（因為其中序遍歷的后一個節點是其父節點），繼續彈出，直到不相等，就說明該節點是所彈出節點的右子樹，設定恰當，將當前節點入堆疊，我們就可以遍歷這個子樹了，
將上述描述轉化為代碼如下：
class Solution1 {
public:
TreeNode*
rebuildTree(const std::vector<int>& preOrder, const std::vector<int>& inOrder) {
long inIdx = 0; // 用于遍歷中序遍歷序列
long preSz = preOrder.size();
std::stack<TreeNode*> parents;
TreeNode* root = new TreeNode(preOrder[0]);
parents.push(root);
for (long preIdx = 1; preIdx < preSz; ++preIdx) {
TreeNode* curNode = new TreeNode(preOrder[preIdx]);
if (parents.top()->val != inOrder[inIdx]) {
// 如果堆疊頂元素值和前序遍歷的值不同，
// 就說明還沒有到左子樹的最左邊
parents.top()->left = curNode;
parents.push(curNode);
} else {
// 已經到了左子樹的最左邊
// 查看堆疊中的下一個值和中序遍歷的下一個值是否相等
// 如果相等，則說明堆疊頂元素沒有右孩子（因為中序遍歷的下一個值是其父節點）
// 則繼續彈出節點，直至不相等
TreeNode* poped;
while (!parents.empty() // 被pop的是根節點
&& parents.top()->val == inOrder[inIdx]) {
poped = parents.top();
parents.pop();
++inIdx;
}
poped->right = curNode;
parents.push(curNode);
}
}
return root;
}
};
驗證
可以將恢復后的子樹中序（或者先序）列印對比（或者保存對比），以驗證我們確實恢復了二叉樹，
下面提供Morris方法中序遍歷一個二叉樹并將其列印的代碼：
void
MorrisInOrder(TreeNode* root) {
TreeNode* cur = root;
TreeNode* rightest;
while (cur != nullptr) {
if (cur->left) {
rightest = cur->left;
while(rightest->right && rightest->right != cur) {
rightest = rightest->right;
}
if(rightest->right == nullptr) {
rightest->right = cur;
cur = cur->left;
continue;
} else { // rightest->right == cur;
rightest->right = nullptr;
}
}
std::cout << cur->val << ' ';
cur = cur->right;
}
std::cout << '\n';
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/539245.html
標籤：其他
下一篇：力扣13 羅馬數字轉為整數