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;
    }
};

本文由 Rust401 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Mar 28, 2019 at 03:36 am