0144 Binary Tree Preorder Traversal

Problem Description

Given the root of a binary tree, return the preorder traversal of its nodes' values.

Example

Input: root = [1,null,2,3]
Output: [1,2,3]

Solution

Please refer this post for more details on the BST and traversal methods. Please observe that this problem is quite related to the Inorder Traversal Problem, especially on the recursive method. Actually you can also adjust a bit on code of the iterative and Morris method from the inorder problem to get the correct preorder traversal code. Check details below.

Recursive Method

The simplest solution.

vector<int> ret;
vector<int> preorderTraversal(TreeNode* root) { //resursively
        preorder(root);
        return ret;
    }
    
    void preorder(TreeNode* root){
        if(!root) return;
        ret.push_back(root->val);
        preorder(root->left);
        preorder(root->right);
    }

Iterative Method with stack

This method basically ask you to explictly use the stack to simulate the recursive call in the recursive method. You could write the code following the logic/execution flow from the recursive method. We also want to point out the relation to the Inorder Tranversal problem.

vector<int> preorderTraversal(TreeNode* root) { //iteratively
        vector<int> ret;
        stack<TreeNode*> stk;
        while(root||stk.size()>0) {
            while(root){
                ret.push_back(root->val); // the only difference, move it outside while loop if solving inorder traversa
                stk.push(root);
                root = root->left;
            }
            root = stk.top();
            stk.pop();
            root = root->right;
        }
        return ret;
    }

Morris Method

This is method is advantageous in that it only uses constant space instead of O(n) or O(lg(n)) space. If you could write out the morris code for inorder traversal problem, you can just move one line of code around to get this problem solved.

vector<int> preorderTraversal(TreeNode* root) { //Morris method: very simliar to the inorder traversal
        vector<int> ret;
        TreeNode* curr = root, *pre;
        while(curr){
            pre = curr->left;
            if(pre){
                while(pre->right && pre->right!=curr) pre = pre->right; // get the predecessor of curr Node
                if(!pre->right){ // link
                    pre->right = curr;
                    ret.push_back(curr->val); // only difference with inorder tranversal, should be moved below
                    curr = curr->left;
                }else{ // encounter the visited node,need to remove the added link
                    pre->right = nullptr;
                    curr = curr->right;
                }
            }else {
                ret.push_back(curr->val);
                curr = curr->right;
            }
        }
        return ret;
    }