# Binary Tree Preorder Traversal

## Question

### Problem Statement

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

For example:
Given binary tree {1,#,2,3},

   1
\
2
/
3


return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

## 题解1 - 递归

### Python - Divide and Conquer

"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
this.val = val
this.left, this.right = None, None
"""

class Solution:
"""
@param root: The root of binary tree.
@return: Preorder in ArrayList which contains node values.
"""
def preorderTraversal(self, root):
if root == None:
return []
return [root.val] + self.preorderTraversal(root.left) \
+ self.preorderTraversal(root.right)


### C++ - Divide and Conquer

/**
* Definition of TreeNode:
* class TreeNode {
* public:
*     int val;
*     TreeNode *left, *right;
*     TreeNode(int val) {
*         this->val = val;
*         this->left = this->right = NULL;
*     }
* }
*/

class Solution {
public:
/**
* @param root: The root of binary tree.
* @return: Preorder in vector which contains node values.
*/
vector<int> preorderTraversal(TreeNode *root) {
vector<int> result;
if (root != NULL) {
// Divide
vector<int> left = preorderTraversal(root->left);
vector<int> right = preorderTraversal(root->right);
// Merge
result.push_back(root->val);
result.insert(result.end(), left.begin(), left.end());
result.insert(result.end(), right.begin(), right.end());
}

return result;
}
};


### C++ - Traversal

/**
* Definition of TreeNode:
* class TreeNode {
* public:
*     int val;
*     TreeNode *left, *right;
*     TreeNode(int val) {
*         this->val = val;
*         this->left = this->right = NULL;
*     }
* }
*/

class Solution {
public:
/**
* @param root: The root of binary tree.
* @return: Preorder in vector which contains node values.
*/
vector<int> preorderTraversal(TreeNode *root) {
vector<int> result;
traverse(root, result);

return result;
}

private:
void traverse(TreeNode *root, vector<int> &ret) {
if (root != NULL) {
ret.push_back(root->val);
traverse(root->left, ret);
traverse(root->right, ret);
}
}
};


### Java - Divide and Conquer

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
if (root != null) {
// Divide
List<Integer> left = preorderTraversal(root.left);
List<Integer> right = preorderTraversal(root.right);
// Merge
}

return result;
}
}


### Java - Traversal

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
private List<Integer> result = new ArrayList<Integer>();

public List<Integer> preorderTraversal(TreeNode root) {
if (root != null) {
preorderTraversal(root.left);
preorderTraversal(root.right);
}

return result;
}
}


## 题解2 - 迭代

### Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
# @param {TreeNode} root
# @return {integer[]}
def preorderTraversal(self, root):
if root is None:
return []

result = []
s = []
s.append(root)
while s:
root = s.pop()
result.append(root.val)
if root.right is not None:
s.append(root.right)
if root.left is not None:
s.append(root.left)

return result


### C++

/**
* Definition of TreeNode:
* class TreeNode {
* public:
*     int val;
*     TreeNode *left, *right;
*     TreeNode(int val) {
*         this->val = val;
*         this->left = this->right = NULL;
*     }
* }
*/

class Solution {
public:
/**
* @param root: The root of binary tree.
* @return: Preorder in vector which contains node values.
*/
vector<int> preorderTraversal(TreeNode *root) {
vector<int> result;
if (root == NULL) return result;

stack<TreeNode *> s;
s.push(root);
while (!s.empty()) {
TreeNode *node = s.top();
s.pop();
result.push_back(node->val);
if (node->right != NULL) {
s.push(node->right);
}
if (node->left != NULL) {
s.push(node->left);
}
}

return result;
}
};


### Java

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();

Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
if (root != null) stack.push(root);
while (!stack.isEmpty()) {
root = stack.pop();
if (root.right != null) stack.push(root.right);
if (root.left != null) stack.push(root.left);
}

return result;
}
}


### 源码分析

1. 对root进行异常处理
2. 将root压入栈
3. 循环终止条件为栈s为空，所有元素均已处理完
4. 访问当前栈顶元素(首先取出栈顶元素，随后pop掉栈顶元素)并存入最终结果
5. 将右、左节点分别压入栈内，以便取元素时为先左后右。
6. 返回最终结果