# 144.Binary-Tree-Preorder-Traversal

## ้ข็ฎๅฐๅ

https://leetcode.com/problems/binary-tree-preorder-traversal/

## ้ข็ฎๆ่ฟฐ

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

Example:
Input: [1,null,2,3]
1
\
2
/
3

Output: [1,2,3]
Follow up: Recursive solution is trivial, could you do it iteratively?``````

## ไปฃ็ 

### Approach #1 Recurion

``````class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
dfs(root, ans);
return asn;
}

private void dfs(TreeNode root, List<Integer> ans) {
if (root == null)    return;
dfs(root.left, ans);
dfs(root.right, ans);
}
}``````

### Approach #2 Iterations

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
if (root == null)    return output;

while (!stack.isEmpty()) {
TreeNode node = stack.pollLast();
if (node.right != null) {
}
if (node.left != null) {
}
}
return output;
}
}``````

### Approach #3 Morris Traversal Confusion

``````class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
TreeNode node = root;
while (node != null) {
if (node.left == null) {
node = node.right;
} else {
TreeNode predecessor = node.left;
while ((predecessor.right != null) && (predecessor.right != node)) {
predecessor = predecessor.right;
}

if (predecessor.right == null) {
predecessor.right = node;
node = node.left;
} else {
predecessor.right = null;
node = node.right;
}
}
}

return output;
}
}``````

Last updated