详细思路
六星图class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int>ans; stack<TreeNode*>stk; while(!stk.empty()||root){ while(root){ ans.push_back(root->val); stk.push(root); root=root->left; } root=stk.top();stk.pop(); root=root->right; } return ans; } };踩过的坑 root=stk.top();stk.pop(); root=root->right; top之后跟着pop,因为中左右,从左回到中已经不需要中了,pop中 详细思路 莫里斯遍历,和中序莫里斯唯一的不同是一个在上升期更新答案,一个在下降期更新答案 都需要在没有左孩子时更新答案并通过上升箭头上升
class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> ans; TreeNode *pre,*cur=root; while (cur) { if (cur->left) { //找到pre //如果pre->right不存在说明是下降期,需要更新答案连接pre并去下一个节点 //如果pre->right为cur说明是上升期,需要断开pre去下一个节点,当上升期结束正好下一个节点就是cur->next pre = cur->left; while (pre->right&&pre->right != cur)pre = pre->right; if (!pre->right) { ans.push_back(cur->val); pre->right = cur; cur = cur->left; } else if(pre->right==cur){ pre->right = nullptr; cur = cur->right; } } //如果没有左孩子,说明需要更新答案通过上升箭头上升 else if(!cur->left){ ans.push_back(cur->val); cur = cur->right; } } return ans; } };