leetcode problems

145. Binary Tree Postorder Traversal

Binary Tree traversal problem. First comes an example

leet code serialize: 1,2,3,4,5,6

postorder: 4,5,2,6,4,1

Strategies.

Depth First Search

All types of traversal(preorder, inorder, postorder) follow the rule that onece we goes to a non-leaf node, we don’t go back to parent until the whole sub-tree is travered. So The only strategy is to use depth first search.

##Implementation.

Implementation is fully discussed online, here I just note a funny truth I met when implementing with iteration.

There are two strategies when we meet branch.

1. When we meet branch, push both child into stack(left one on top) and handle right child when it becomes top.
2. When we meet branch, we push left child into stack and go on, we handle right child when root becomes top again.

These too strategy actually lead to the same push() and pop() time since all nodes are pushed and popped only once. The only difference is the space complexity. We hold place for right child that is not visited, so the maximum size of stack may become twice as that in strategy 2.

So it’s actually better to use strategy 2.

##Code Record

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> res;
    if(root == nullptr) return res;
    stack<TreeNode*> s;
    s.push(root);
    TreeNode* prev = root;
    while(!s.empty()){
        TreeNode* top = s.top();
        // strategy 2 start
        if(prev == top && top->left != nullptr) s.push(top->left);
        else if(prev != top->right && top->right != nullptr) s.push(top->right);
        // strategy 2 end
        /* strategy 1 start
        if(prev != top->left && prev != top->right){
            if(top->right != nullptr) s.push(top->right);
            if(top->left != nullptr) s.push(top->left);
        } strategy 1 end
        */
        prev = s.top();
        if(top == s.top()){
            s.pop();
            res.push_back(top->val);
        }else prev = s.top();
    }
    return res;
}

Similiar problems

• (144) Binary Tree Preorder Traversal