LeetCode题目详解——Binary Tree Inorder Traversal

   1
    \
     2
    /
   3

class Solution {
public:
    vector<int> inorderTraversal(TreeNode *root) {
        stack<TreeNode*> rest;
        vector<int> result;
        rest.push(root);
        TreeNode *cur;

        if(root == NULL)
            return result;
        cur=root;
        while(!rest.empty() || cur)
        {
            while (cur) {
                rest.push(cur);
                cur = cur->left;
            }
            if(!rest.empty())
            {
                cur = rest.top();
                result.push_back(cur->val);
                rest.pop();
                cur=cur->right;
            }
        }
        return result;
    }
};

不使用栈的方法即morris方法，利用改变树的结构，来记录接下来需要访问的节点。morris方法的先序遍历和中序遍历很相似，只有一句代码的位置不一样。对于morris方法不太了解的同学可以参考的前一篇文章：LeetCode题目详解——Binary Tree Preorder Traversal 代码如下：

class Solution {
public:
    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> result;
        TreeNode *p=root;
        if(!root)
            return result;
        while(p)
        {
            if(p->left==NULL)
            {
                result.push_back(p->val);
                p=p->right;
            }
            else
            {
                TreeNode *tmp=p->left;
                while(tmp->right && tmp->right!=p)
                {
                    tmp=tmp->right;
                }
                if(tmp->right==NULL)
                {
                    tmp->right=p;
                    p=p->left;
                }
                else
                {
                    result.push_back(p->val);//只有这句代码的位置和先序遍历的时候不太一样
                    tmp->right=NULL;
                    p=p->right;
                }
            }
        }
        return result;
    }
    
};