本題要求常量空間解決問(wèn)題雾家，所以有了是否常量空間內(nèi)遍歷整棵二叉樹的方法。即Morris traversal.

1. 資料

Morris Traversal方法遍歷二叉樹（非遞歸，不用棧氓轰，O(1)空間）

2. 使用了morris 方法的中序遍歷庞呕，accepted

94. Binary Tree Inorder Traversal

//
//  main.cpp
//  leetcode
//
//  Created by YangKi on 15/11/19.
//  Copyright ? 2015年 YangKi. All rights reserved.
#include<vector>
#include<algorithm>
#include<cstdio>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <string>
#include <set>
#include <cstdlib>
#include <queue>
#include <stack>
#include <sstream>
#include <map>
#include <deque>
using namespace std;

class Solution {
    
    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    
    void morrisInOrderT(TreeNode* root, vector<int>& res) {
        TreeNode* current = root;
        TreeNode* prev = NULL;
        
        while (current) {
            if (current->left == NULL) {
                res.push_back(current->val);
                current = current->right;
            }
            else {
                prev = current->left;
                
                while (prev->right != NULL && prev->right != current) {
                    prev = prev->right;
                }
                
                if (prev->right == NULL) {
                    prev->right = current;
                    current = current->left;
                }
                else {
                    // 恢復(fù)結(jié)構(gòu)
                    prev->right = NULL;
                    // 左邊遍歷完了，可以訪問(wèn)中間的那個(gè)了
                    res.push_back(current->val);
                    current = current->right;
                }
            }
        }
    }
    
public:
    
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int>res;
        if (!root) return res;
        
        morrisInOrderT(root, res);
        
        return res;
    }
};

3. 使用了morris 方法來(lái)解決本題

//
//  l_99.cpp
//  leetcode
//
//  Created by YangKi on 2017/1/15.
//  Copyright ? 2017年 YangKi. All rights reserved.
//

#include<vector>
#include<algorithm>
#include<cstdio>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <string>
#include <set>
#include <cstdlib>
#include <queue>
#include <stack>
#include <sstream>
#include <map>
#include <deque>
using namespace std;

class Solution {
    
    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    
    void morrisInOrderT(TreeNode* root, vector<TreeNode*>& nodes) {
        TreeNode* current = root;
        TreeNode* prev = NULL;
        
        TreeNode* lastNodes = new TreeNode(INT_MIN);
        
        while (current) {
            if (current->left == NULL) {
                if (lastNodes->val > current->val) {
                    nodes.push_back(lastNodes);
                    nodes.push_back(current);
                }
                lastNodes = current;
                
                
                current = current->right;
                
            }
            else {
                prev = current->left;
                
                while (prev->right != NULL && prev->right != current) {
                    prev = prev->right;
                }
                
                if (prev->right == NULL) {
                    prev->right = current;
                    current = current->left;
                }
                else {
                    // 恢復(fù)結(jié)構(gòu)
                    prev->right = NULL;
                    
                    // 左邊遍歷完了仗考，可以訪問(wèn)中間的那個(gè)了
                    if (lastNodes->val > current->val) {
                        nodes.push_back(lastNodes);
                        nodes.push_back(current);
                    }
                    lastNodes = current;
                    
                    
                    current = current->right;
                }
            }
        }
    }
    
public:
    
    void recoverTree(TreeNode* root) {
        if (!root) return;
        
        vector<TreeNode*>nodes;
        morrisInOrderT(root, nodes);
        
        if (nodes.size() == 2) {
            int temp = nodes[0]->val;
            nodes[0]->val = nodes[1]->val;
            nodes[1]->val = temp;
        }
        else if (nodes.size() == 4) {
            int temp = nodes[0]->val;
            nodes[0]->val = nodes[3]->val;
            nodes[3]->val = temp;
        }
        
        return;
    }
};