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