#include "leetcode.h" class Solution { public: vector preorderTraversal(TreeNode *root) { // morris traversal vector nodes; while (root) { if (root->left) { TreeNode *pre = root->left; while (pre->right && pre->right != root) pre = pre->right; if (!pre->right) { pre->right = root; nodes.push_back(root->val); root = root->left; } else { pre->right = NULL; root = root->right; } } else { nodes.push_back(root->val); root = root->right; } } return nodes; } };