二叉树的前序遍历

递归：

class Solution {
public:
	vector<int> preorderTraversal(TreeNode* root)
    {
        vector<int> v;
        pre(root, v);
        return v;
	}
    void pre(TreeNode* root, vector<int>& v)
    {
        if (!root)
            return;
        v.push_back(root->val);
        pre(root->left,v);
        pre(root->right, v);
    }
};

迭代：

class Solution {
public:
	vector<int> preorderTraversal(TreeNode* root)
    {
        vector<int> ret;
        stack<TreeNode*> s;
        //当栈不为空或者root不为空的时候进入while循环
        while (!s.empty() || root)
        {
            while (root)
            {
                s.push(root);
                ret.push_back(root->val);
                root = root->left;
            }
            root = s.top()->right;
            s.pop();
         }
        return ret;
	}
};

Morris 遍历
思路与算法

class Solution {
public:
    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }

        TreeNode *p1 = root, *p2 = nullptr;

        while (p1 != nullptr) {
            p2 = p1->left;
            if (p2 != nullptr) {
                while (p2->right != nullptr && p2->right != p1) {
                    p2 = p2->right;
                }
                if (p2->right == nullptr) {
                    res.emplace_back(p1->val);
                    p2->right = p1;
                    p1 = p1->left;
                    continue;
                } else {
                    p2->right = nullptr;
                }
            } else {
                res.emplace_back(p1->val);
            }
            p1 = p1->right;
        }
        return res;
    }
};

大佬对mirror遍历的解释
颜色表记法：
颜色标记法详解

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
      vector<int> ret;
         stack<pair<string, TreeNode*>> s;
         if (root == NULL)
             return ret;
         s.push({"white",root});
         while (!s.empty())
         {
             pair<string,TreeNode*> temp=s.top();
             s.pop();
             if (temp.second == NULL)
                 continue;
             if (temp.first == "white")
             {
                 if (temp.second->right == NULL && temp.second->left == NULL)
                 {
                     s.push({ "grey",temp.second });
                 }
                 else
                 {
                     temp.first = "grey";
                     s.push({ "white", temp.second->right });
                    s.push({ "white", temp.second->left });
                     s.push(temp);
                 }
             }
             else
             {
                 ret.push_back(temp.second->val);
             }
         }
         return ret;
    }
};