Morris二叉树遍历算法

Morris二叉树遍历算法
时间复杂度O（N），空间复杂度O（1）
这种方法借鉴了线索化二叉树的思想，但是不占用空间

中序遍历方法如下：

1. 如果当前节点的左孩子为空，则输出当前节点并将其右孩子作为当前节点。

2. 如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点。

   a) 如果前驱节点的右孩子为空，将它的右孩子设置为当前节点。当前节点更新为当前节点的左孩子。

   b) 如果前驱节点的右孩子为当前节点，将它的右孩子重新设为空（恢复树的形状）。输出当前节点。当前节点更新为当前节点的右孩子。

3. 重复以上1、2直到当前节点为空。

图例如下：

代码如下

/**
 1. Definition for a binary tree node.
 2. struct TreeNode {
 3.     int val;
 4.     TreeNode *left;
 5.     TreeNode *right;
 6.     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 7. };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root)
    {
        vector<int> res;
        TreeNode *cur = root, *prev = nullptr;
        while (cur)
        {
            if (cur->left == nullptr)
            {
                res.push_back(cur->val);
                cur = cur->right;
            }
            else
            {
                prev = cur->left;
                while (prev->right != nullptr && prev->right != cur)
                    prev = prev->right;

                if (prev->right == nullptr)
                {
                    prev->right = cur;
                    cur = cur->left;
                }
                else
                {
                    res.push_back(cur->val);
                    prev->right = nullptr;
                    cur = cur->right;
                }
            }
        }

        return res;
    }
};

前序遍历方法如下

1. 如果当前节点的左孩子为空，则输出当前节点并将其右孩子作为当前节点。

2. 如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点

   a). 如果前驱节点的右孩子为空，将它的右孩子设置为当前节点。输出当前节点（代码只有这一行不同），当前节点更新为当前节点的左孩子。

   b).如果前驱节点的右孩子为当前节点，将它的右孩子重新设为空。当前节点更新为当前节点的右孩子。

3. 重复以上1、2直到当前节点为空。

示例图：

代码如下

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root)
    {
        vector<int> res;
        TreeNode *cur = root, *prev = nullptr;
        while (cur)
        {
            if (cur->left == nullptr)
            {
                res.push_back(cur->val);
                cur = cur->right;
            }
            else
            {
                prev = cur->left;
                while (prev->right != nullptr && prev->right != cur)
                    prev = prev->right;

                if (prev->right == nullptr)
                {
                    prev->right = cur;
                    res.push_back(cur->val);
                    cur = cur->left;
                }
                else
                {
                    prev->right = nullptr;
                    cur = cur->right;
                }
            }
        }

        return res;
    }
};

再来看LeetCode99. Recover Binary Search Tree
Q:

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（N）空间复杂度很容易想到，将所有节点保存入数组中，遍历即可
这里要求O（1）空间复杂度，所以想到Morris中序遍历

AC解：

/**
  *     Morris中序遍历，用一组pair存贮第一个和第二个节点
  * 
  */
class Solution 
{
public:
    void recoverTree(TreeNode* root) 
    {
        TreeNode *cur = root, *prev = nullptr;
        pair<TreeNode*, TreeNode*> pa;
        while (cur)
        {
            if (cur->left == nullptr)
            {
                detect(pa, prev, cur);
                prev = cur;
                cur = cur->right;
            }
            else
            {
                TreeNode *node = cur->left;             //prev须时刻为当前遍历节点前驱，用于之后的比较
                while (node->right != nullptr && node->right != cur)//所以这里需要有一个node节点用于后面的改造
                    node = node->right;

                if (node->right == nullptr)
                {
                    node->right = cur;
                    cur = cur->left;
                }
                else
                {
                    detect(pa, prev, cur);
                    node->right = nullptr;
                    prev = cur;
                    cur = cur->right;
                }
            }
        }

        swap(pa.first->val, pa.second->val);
    }

    void detect(pair<TreeNode*, TreeNode*>& pa, TreeNode *prev, TreeNode *cur)
    {
        if (prev != nullptr && prev->val > cur->val)
        {
            if (pa.first == nullptr)
                pa.first = prev;

            pa.second = cur;

        }
    }
};

引用了Morris二叉树遍历算法，对作者表示感谢！