144. Binary Tree Preorder Traversal.md

8/17/2021

144. Binary Tree Preorder Traversal

The algorithms are similar as 94. Inorder Traversal.

1. Recursion Method

C++

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        helper(root, ans);
        return ans;
    }
    void helper(TreeNode* root, vector<int>& ans){
        if(!root){
            return;
        }
        ans.push_back(root->val);
        helper(root->left, ans);
        helper(root->right, ans);
    }
};

Python

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans = []
        self.helper(root, ans)
        return ans
    
    def helper(self, root, ans):
        if not root:
            return
        ans.append(root.val)
        self.helper(root.left, ans)
        self.helper(root.right, ans)

2. Iterative Method Using Stack

• Go all the way to the left and push every element.

C++

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        TreeNode* cur = root;
        stack<TreeNode*> treeStack;
        while(cur || !treeStack.empty()){
            while(cur){
                treeStack.push(cur);
                ans.push_back(cur->val);
                cur = cur->left;
            }
            cur = treeStack.top();
            treeStack.pop();
            cur = cur->right;
        }
        return ans;
    }
};

Python

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans = []
        treeStack = []
        cur = root
        while cur or treeStack:
            # add cur to stack and go all the way to the left
            while cur:
                ans.append(cur.val)
                treeStack.append(cur)
                cur = cur.left
            cur = treeStack.pop()
            cur = cur.right
        return ans

3. The Second Way of Using A Stack

• pop first and add it to ans
• push right and push left

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        stack1 = []
        ans = []
        stack1.append(root)
        while stack1:
            cur = stack1.pop()
            ans.append(cur.val)
            # or using if not top, continue
            if cur.right:
                stack1.append(cur.right)
            if cur.left:
                stack1.append(cur.left)
        
        return ans