描述
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?
分析
二叉排序树中,两个节点被交换了,要求写一个算法,将该树恢复成二叉排序树。如果用中序遍历,得到一个序列,可以很快找到交换的两个节点,调整之后再生成树,但题目要求空间复杂度是O(1).
实际上可以用pre指向中序遍历过程中的前一个节点,如果找到了次序错误的节点,那么pre指向的就是第一个次序错误的节点,如果二叉排序树中交换的节点不是相邻的,那么之后的遍历过程中肯定还能找到次序错误的节点,这时就可以找到第二个次序错误的节点了。
解决方案1(C++)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
|
class Solution { public: TreeNode *res1, *res2; TreeNode* pre; void recoverTree(TreeNode* root) { if(!root) { return; } res1 = res2 = pre = NULL; in_order(root); swap(res1->val, res2->val); } void in_order(TreeNode* root) { if(!root) { return; } if(root->left) { in_order(root->left); } if(pre && root->val < pre->val) { if(res1 == NULL) { res1 = pre; res2 = root; }else { res2 = root; } } pre = root; if(root->right) { in_order(root->right); } } };
|