144. Binary Tree Preorder Traversal

Description

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

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: [1, null, 2, 3]

Output: [1, 2, 3]

Solutions

TreeNode

// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode() {}
    
    TreeNode(int val) { this.val = val; }
    
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> nodes = new ArrayList();
        helper(root, nodes);
        return nodes;
    }
    
    private void helper(TreeNode node, List<Integer> nodes) {
        if(node == null) return;
        nodes.add(node.val);
        helper(node.left, nodes);
        helper(node.right, nodes);
    }
}

Solution 2

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList();
        
        LinkedList<TreeNode> stack = new LinkedList();
        stack.add(root);
        
        while(!stack.isEmpty()) {
            TreeNode tmp = stack.pollLast();
            result.add(tmp.val);
            if(tmp.right != null) {
                stack.add(tmp.right);
            }
            if(tmp.left != null) {
                stack.add(tmp.left);
            }
        }
        
        return result;
    }
}

Follow up