99. Recover Binary Search Tree-白红宇

99. Recover Binary Search Tree

阅读量：6006 次

发布时间：2019-06-20

本文共 2095 字，大约阅读时间需要 6 分钟。

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    \     5The above binary tree is serialized as"{1,2,3,#,#,4,#,#,5}".

解析

一种非递归且不使用栈，空间复杂度为O(1)的遍历方法

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);        }    }};