BST的遍历
in Solutions with 31121 comments

BST的遍历

in Solutions with 31121 comments

BST的遍历

InOrder

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) 
    {
        vector<int> result;
        if(root==NULL)return result;
        stack<TreeNode*> aStack;
        TreeNode* cur=root;
        
        while(cur!=NULL||!aStack.empty())
        {
            while(cur!=NULL)
            {
                aStack.push(cur);
                cur=cur->left;
            }
            cur=aStack.top();
            aStack.pop();
            result.push_back(cur->val);
            cur=cur->right;
        }
        return result;
    }
};

PreOrder

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) 
    {
        vector<int> result;
        if(root==NULL)return result;
        stack<TreeNode*> aStack;
        TreeNode* cur=root;
        
        while(cur!=NULL||!aStack.empty())
        {
            while(cur!=NULL)
            {
                result.push_back(cur->val);
                aStack.push(cur);
                cur=cur->left;
            }
            cur=aStack.top();
            aStack.pop();
            cur=cur->right;
        }
        return result;
    }
};

PostOrder

后序遍历其实相当于先访问根节点,再访问右子树,最后访问左子树。然后把得到的序列整个reverse即可得到结果。这边用了deque,避免了reverse,插入开销为O(1)

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) 
    {
        deque<int> result;
        if(root==NULL)return {};
        stack<TreeNode*> aStack;
        TreeNode* cur=root;
        while(cur||!aStack.empty())
        {
            while(cur)
            {
                result.push_front(cur->val);
                aStack.push(cur);
                cur=cur->right;
            }
            cur=aStack.top;
            aStack.pop();
            cur=cur->left;
        }
        vector<int> realResult(result.begin(),result.end());
        return realResult;
    }
};

Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 20480 bytes) in /www/wwwroot/rust401.com/var/Typecho/Db/Adapter/Pdo.php on line 119