Tree travisal

Preorder

Just do normal DFS:

  • output cur
  • push cur->right
  • push cur->left

Because we use stack, cur will visit the last pushed node.
For preorder traversal, it is this -> left -> right.
Thus, we should push the left child to the stack later.
















vector<int> preorderTraversal(TreeNode* root) {
    vector<int> ans;
    TreeNode* cur = root;
    stack<TreeNode*> s;
    while (cur || !s.empty()) {
        if (cur) {
            ans.push_back(cur->val);
            s.push(cur->right);
            s.push(cur->left);
        } 
        cur = s.top(); s.pop();
    }

    return ans;
}

Postorder

2 stack (simpler)

Do mirrored inorder traversal and reverse the results:

std::reserve: http://www.cplusplus.com/reference/algorithm/reverse/

Note that insert for vector is O(N) instead of O(1) for push_back
















vector<int> postorderTraversal(TreeNode* root) {
    vector<int> ans;
    stack<TreeNode*> s;
    TreeNode* cur = root;
    while (cur || !s.empty()) {
        if (cur) {
            ans.push_back(cur->val);
            s.push(cur->left);
            s.push(cur->right);
        } 
        cur = s.top(); s.pop();
    }
    reverse(ans.begin(),ans.end());
    return ans;
}

no extra space

























vector<int> postorderTraversal(TreeNode* root) {
    vector<int> ans;
    stack<TreeNode*> s;  // no null in stack
    TreeNode* cur = root;
    while (cur || !s.empty()) {
        if (cur) {
            if (cur->right) s.push(cur->right);
            s.push(cur);
            cur = cur-> left;
        } else {
            cur = s.top(); s.pop();
            // make sure cur->right is processed before cur
            if (cur->right && !s.empty() && cur->right == s.top()) {
                s.pop();
                s.push(cur);
                cur = cur->right; 
            } else {
                ans.push_back(cur->val);
                cur = NULL; // always process node from stack
            }
        }
    }
    return ans;
}

Inorder




















vector<int> inorderTraversal(TreeNode* root) {
    vector<int> ans;
    stack<TreeNode*> s;
    TreeNode* cur = root;
    while (!s.empty() || cur) {
        // check and add left child
        if (cur) {
            s.push(cur);
            cur = cur-> left;
        } else {
            // reach the left end OR cur (parent->right) is null
            // output from stack and go to right child
            cur = s.top(); s.pop();
            ans.push_back(cur->val);
            cur = cur->right;
        }
    }
    return ans;
}

Level-order

simple BFS:
















vector<int> preorderTraversal(TreeNode* root) {
    vector<int> ans;
    TreeNode* cur = root;
    queue<TreeNode*> q;
    while (cur || !q.empty()) {
        if (cur) {
            ans.push_back(cur->val);
            q.push(cur->left);
            q.push(cur->right);
        } 
        cur = q.front(); q.pop();
    }

    return ans;
}
Select a repo