Leetcode 144. Binary Tree Preorder Traversal

Description:

Given a binary tree, return the preorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3}.

return [1,2,3].

Thinking:

One of the forms of DFS.

Steps:

Check whether input is valid
Recursion or Iteration? We can do preorder in both recursive and iterative ways. And the follow steps are the steps if we do it in recursive way.
Do we need to create helper function? It depends on the value we want to return. If we we want to the function return TreeNode not List<Integer>. then we need to create a helper function.
How to do the recurison? Display the data part of the root (or current node). Traverse the left subtree by recursively calling the preorder function. Traverse the right subtree by recursively calling the preorder function.

Determin the return condition

Code:

Iteration:

public class Solution {
 public List<Integer> preorderTraversal(TreeNode root) {
     if(root == null) return new ArrayList<Integer>();
     List<Integer> result = new ArrayList<>();
     Stack<TreeNode> stack = new Stack<>();
     stack.push(root);
     while(!stack.isEmpty()){
         TreeNode current = stack.pop();
         result.add(current.val);
         if(current.right != null) stack.push(current.right);
         if(current.left != null) stack.push(current.left);
     }
     return result;
 }
}
//version 2
public class Solution {
 public List<Integer> preorderTraversal(TreeNode root) {
     if(root == null) return new ArrayList<Integer>();
     List<Integer> result  = new ArrayList<>();
     Stack<TreeNode> stack = new Stack<>();
     TreeNode current = root;
     while(!stack.isEmpty()|| current != null){
         while(current != null){
             result.add(current.val);
             stack.push(current);
             current = current.left;
         }
         current = stack.pop();
         current = current.right;
     }
     return result;
 }
}

Recursion(No helper):

public class Solution {
 public List<Integer> preorderTraversal(TreeNode root) {
     if(root == null) return new ArrayList<Integer>();
     List<Integer> result = new ArrayList<>();
     result.add(root.val);
     List<Integer> left = preorderTraversal(root.left);
     List<Integer> right = preorderTraversal(root.right);
     result.addAll(left);
     result.addAll(right);
     return result;
 }
}

Recursion(with helper):

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

Conclusion:

This is a basic form of DFS that we should know.
when we need to create helper function:
The return value is not we want/ we need more than one return value to solve then problem.(resultType)
The input parameter is not we want(eg.int left, int right), or we need to input the result in the parameter to store all the result(List<Interger> result)

Leetcode 144. Binary Tree Preorder Traversal