Home Computer Science Java Algorithm

[[Lintcode problems]]
URL : 66 · Binary Tree Preorder Traversal - LintCode

# Description

Given a binary tree, return the preorder traversal of its nodes' values.
Example 1:
Input:

binary tree = {1,2,3}

Output:

[1,2,3]

主要的考點是不用 recursion 寫出 preorder
用 stack ＋ while 的方法寫

# Code - Stack

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root: A Tree
     * @return: Preorder in ArrayList which contains node values.
     */
    public List<Integer> preorderTraversal(TreeNode root) {
      Stack<TreeNode> stack = new Stack<>();
      List<Integer> list = new ArrayList<>();
      if(root == null) return list;
      stack.push(root);
      while (!stack.isEmpty()){
          TreeNode node = stack.pop();
          list.add(node.val);
          if (node.right != null){ // 先寫右邊，因為等下 pop 出來是先 pop 左邊，後 pop 右邊
              stack.push(node.right);
          } 
          if (node.left != null){
              stack.push(node.left);
          }
      }
      return list;
    }
}```
# DFS 
```java
 public List<Integer> preorderTraversal(TreeNode root) {
	 List<Integer> result = new ArrayList<>();
	 if (root == null){
		 return result;
	 }
	 
	 result.add(root.val);
	 result.addAll(preorderTraversal(root.left));
	 result.addAll(preorderTraversal(root.right));
	 
	 return result;
}