99. Recover Binary Search Tree

題目

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.
Note:
A solution using O(n ) space is pretty straight forward. Could you devise a constant space solution?


confused what"{1,#,2,3}"means? > read more on how binary tree is serialized on OJ.

OJ's Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.

Here's an example:

   1
  / \
 2   3
    /
   4
    \
     5

The above binary tree is serialized as"{1,2,3,#,#,4,#,#,5}". 
           

解析

• 一種非遞歸且不使用棧，空間複雜度為O(1)的周遊方法
• [LeetCode] Recover Binary Search Tree 複原二叉搜尋樹

class Solution_99 {
public:
	void recoverTree(TreeNode* root) {

		TreeNode* first = NULL, *second = NULL, *parenet = NULL;
		TreeNode*cur, *pre; //中序周遊
		cur = root;

		while (cur)
		{
			if (cur->left==NULL)
			{
				if (parenet&&parenet->val>cur->val)
				{
					if (!first)
					{
						first = parenet;
					}
					second = cur;
				}
				parenet = cur;
				cur = cur->right;
			}
			else
			{
				pre = cur->left; //找到左子樹的最右節點
				while (pre->right&&pre->right!=cur)
				{
					pre = pre->right;
				}

				if (!pre->right)
				{
					pre->right = cur;
					cur = cur->left;
				}
				else
				{
					pre->right = NULL; //恢複樹結構
					if (parenet&&parenet->val > cur->val)
					{
						if (!first)
						{
							first = parenet;
						}
						second = cur;
					}
					parenet = cur;
					cur = cur->right;
				}
			}
		}
		if (first&&second)
		{
			swap(first->val, second->val);
		}
	}
};

           

題目來源

C/C++基本文法學習

STL

C++ primer