Given a binary tree, return the postorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

后序遍历稍微麻烦一点,因为根节点会被多次经过,需要在最后一次经过的时候退栈。我使用hashmap来储存每个节点的状态,当开始right child遍历时,讲其节点状态设置为1。每次到达该结点时检查其状态,如果为1则退栈,将结果放入List,否则向下遍历。

 


class Solution {
public:
        stack<TreeNode*> treeStack;
        unordered_map<TreeNode*, int> treeTraversalMap;
    
        bool checkNode(TreeNode* node)
        {
                if(treeTraversalMap.find(node) == treeTraversalMap.end()) return false;
        
                return treeTraversalMap[node] == 1;
        }
    
        vector<int> postorderTraversal(TreeNode* root) 
        {
                vector<int> res;
                if(root)
                {
                        treeStack.push(root);
                        TreeNode* ptr = root;
                        treeTraversalMap[root] = 0;
            
                        while(!treeStack.empty())
                        {
                                while(ptr->left)
                                {
                                        ptr = ptr->left;
                                        treeStack.push(ptr);
                                }
                
                                while(!ptr->right || checkNode(ptr))
                                {
                                        if(!treeStack.empty())
                                        {
                                                ptr = treeStack.top();
                                                if(!ptr->right || checkNode(ptr))
                                                {
                                                        treeStack.pop();
                                                        res.push_back(ptr->val);
                                                }
                                        }
                                        else
                                        {
                                                ptr = nullptr;
                                                break;
                                        }
                                }
                
                                if(ptr) 
                                {
                                        treeTraversalMap[ptr] = 1;
                                        ptr = ptr->right;
                                        treeStack.push(ptr);
                                }
                        }
                }
        
                return res;
        }
};

Leave a Reply

Your email address will not be published. Required fields are marked *