前序遍历

前序遍历

 

 

详细思路

六星图
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;
    }
};

 

上一篇:java中栈stack和队列queue用法详细分析(全)


下一篇:有效的括号 - 力扣