Recover Binary Search Tree [leetcode]
來源：程序員人生 發布時間：2014-10-02 08:00:01 閱讀次數：2373次
本題是在中序遍歷的基礎上，找不合規范（不是遞增）的樹節點對，然后交換
首先看兩種序列：
1. 1 3 2 4=>應該交換3和2
2. 4 3 2 1=>應交換4和1
這兩種序列對應了不符合條件的BST的中序遍歷序列的所有可能性---兩個節點中序遍歷相鄰/不相鄰
如果我們用一個數組swap保存所有中序遍歷不遞增的結果，那么這個數組只可能是2或者4的大小
而我們交換數組中節點對內容，只需交換第一個和最后一個樹節點對的內容
vector<TreeNode *> swap;
TreeNode * pre;
void recoverTree(TreeNode *root)
{
pre = new TreeNode(-999999);
swap = vector<TreeNode *>();
inorder(root);
if (swap.size() > 1)
{
int val = swap[0]->val;
swap[0]->val = swap[swap.size() - 1]->val;
swap[swap.size() - 1]->val = val;
}
}
void inorder(TreeNode * root)
{
if (root == NULL) return;
inorder(root->left);
if (pre->val > root->val)
{
swap.push_back(pre);
swap.push_back(root);
}
pre = root;
inorder(root->right);
}
由于只交換第一個和最后一個樹節點內容，我們可以只保存第一個和最后一個Node
if(!first) first = pre;
last = root;
替換
swap.push_back(pre); swap.push_back(root);
代碼如下：
TreeNode * first, * last;
TreeNode * pre;
void recoverTree(TreeNode *root)
{
pre = new TreeNode(-999999);
first = last = NULL;
inorder(root);
if (first)
{
int val = first->val;
first->val = last->val;
last->val = val;
}
}
void inorder(TreeNode * root)
{
if (root == NULL) return;
inorder(root->left);
if (pre->val > root->val)
{
if (!first) first = pre;
last = root;
}
pre = root;
inorder(root->right);
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
