程序员代码面试指南 3.5：遍历二叉树的神级方法

1、思路

• 因为遍历二叉树的递归方法实际使用了函数站，非递归的方法使用了申请的栈，两者的额外空间都与树的高度相关，所以空间复杂度为 ， 为二叉树的高度；

• 减少空间复杂度的难点在于从子节点返回父节点，Morris遍历利用了二叉树中大量存在的空闲节点来实现从下层到上层的遍历；

• Morris遍历原理：
  1、若当前节点cur == nullptr，则遍历完结，否则继续下面的过程；
  2、若cur->left == nullptr，则cur = cur->right；
  3、若cur->left != nullptr，则找到cur左子树上最右的节点，记为mostRight：
  3.1）若mostRight->right == nullptr，表示第一次到达cur节点，令mostRight->right = cur，然后cur = cur->left；
  3.2）若mostRight->right == cur，表示第二次到达cur节点，令mostRight->right = nullptr，然后cur = cur->right；

• 在一棵二叉树中，对于有左子树的节点都会到达两次，其余节点只会到达一次。可以根据Morris遍历加工出前中后序遍历；

• 时间复杂度为 ，空间复杂度为 。

2、代码

#include <iostream>
#include <vector>

using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left, *right;
    TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {}
};

//建树
void createTree(TreeNode* root, int &n)
{
    if (n == 0) return;

    int rootVal, leftVal, rightVal;
    cin >> rootVal >> leftVal >> rightVal;

    if (leftVal != 0)
    {
        root->left = new TreeNode(leftVal);
        createTree(root->left, -- n);
    }

    if (rightVal != 0)
    {
        root->right = new TreeNode(rightVal);
        createTree(root->right, -- n);
    }
}

//Morris前序遍历
void morrisPreOrder(TreeNode *root, vector<int> &res)
{
    if (root == nullptr) return;

    TreeNode *cur = root;
    TreeNode *mostRight = nullptr;

    while (cur != nullptr)
    {
        mostRight = cur->left;
        if (mostRight != nullptr)
        {
            while (mostRight->right != nullptr && mostRight->right != cur)    //找到cur左子树的最右节点
            {
                mostRight = mostRight->right;
            }

            if (mostRight->right == nullptr)    //第一次到达cur左子树的最右叶子节点
            {
                mostRight->right = cur;
                res.push_back(cur->val);
                cur = cur->left;                //往左走开始新的第一层while循环
                continue;
            }
            else
            {
                mostRight->right = nullptr;    //第二次到达cur左子树的最右叶子节点
            }
        }
        else
        {
            res.push_back(cur->val);
        }

        cur = cur->right;
    }
}

//Morris中序遍历
void morrisInOrder(TreeNode *root, vector<int> &res)
{
    if (root == nullptr) return;

    TreeNode *cur = root;
    TreeNode *mostRight = nullptr;

    while (cur != nullptr)
    {
        mostRight = cur->left;
        if (mostRight != nullptr)
        {
            while (mostRight->right != nullptr && mostRight->right != cur)
            {
                mostRight = mostRight->right;
            }

            if (mostRight->right == nullptr)
            {
                mostRight->right = cur;
                cur = cur->left;
                continue;
            }
            {
                mostRight->right = nullptr;
            }
        }

        res.push_back(cur->val);
        cur = cur->right;
    }
}

TreeNode* reverseEdge(TreeNode *root)            //类似反转链表
{
    TreeNode *pre = nullptr, * cur = root, *next = nullptr;

    while (cur != nullptr)
    {
        next = cur->right;
        cur->right = pre;
        pre = cur, cur = next;
    }

    return pre;
}

void printEdge(TreeNode *root, vector<int> &res)
{
    TreeNode *tail = reverseEdge(root);    //反转左子树的右边界
    TreeNode *cur = tail;

    while (cur != nullptr)
    {
        res.push_back(cur->val);
        cur = cur->right;
    }

    reverseEdge(tail);                    //还原左子树的右边界
}

//Morris后序遍历
void morrisPostOrder(TreeNode *root, vector<int> &res)
{
    if (root == nullptr) return;

    TreeNode *cur = root;
    TreeNode *mostRight = nullptr;

    while (cur != nullptr)
    {
        mostRight = cur->left;
        if (mostRight != nullptr)
        {
            while (mostRight->right != nullptr && mostRight->right != cur)
            {
                mostRight = mostRight->right;
            }

            if (mostRight->right == nullptr)  //第一次达到：不打印
            {
                mostRight->right = cur;
                cur = cur->left;
                continue;
            }
            else
            {
                mostRight->right = nullptr;
                printEdge(cur->left, res);    //第二次到达：逆序打印左子树的右边界
            }
        }

        cur = cur->right;
    }

    printEdge(root, res);
}

int main()
{
    int n, rootVal;
    cin >> n >> rootVal;

    TreeNode *root = new TreeNode(rootVal);
    createTree(root, n);

    vector<int> res;
    morrisPreOrder(root, res);
    for (int &i : res) cout << i << " ";
    cout << endl;

    res.clear();
    morrisInOrder(root, res);
    for (int &i : res) cout << i << " ";
    cout << endl;

    res.clear();
    morrisPostOrder(root, res);
    for (int &i : res) cout << i << " ";
    cout << endl;

    return 0;
}