# 144. Binary Tree Preorder Traversal 二叉树的前序遍历

@TOC

## # 题目描述

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?

## # 解题方法

### # 递归

python代码如下：

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

class Solution(object):
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if not root: return []
res = []
res.append(root.val)
res.extend(self.preorderTraversal(root.left))
res.extend(self.preorderTraversal(root.right))
return res

Java代码如下：

public class Solution {
List<Integer> ans = new ArrayList<Integer>();
public List<Integer> preorderTraversal(TreeNode root) {
preOrder(root);
return ans;
}
public void preOrder(TreeNode root){
if(root == null){
return;
}
preOrder(root.left);
preOrder(root.right);
}
}

C++代码如下：

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
preorder(root, res);
return res;
}
void preorder(TreeNode* root, vector<int>& res) {
if (!root) return;
res.push_back(root->val);
preorder(root->left, res);
preorder(root->right, res);
}
};

### # 迭代

Python代码如下：

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

class Solution(object):
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if not root: return []
res = []
stack = []
stack.append(root)
while stack:
node = stack.pop()
if not node:
continue
res.append(node.val)
stack.append(node.right)
stack.append(node.left)
return res

Java代码如下：

public class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
if(root == null){
return new ArrayList<Integer>();
}
List<Integer> ans = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode temp = stack.pop();
if(temp.right != null){
stack.push(temp.right);
}
if(temp.left != null){
stack.push(temp.left);
}
}
return ans;
}
}

C++代码如下：

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> s;
s.push(root);
while (!s.empty()) {
auto node = s.top(); s.pop();
if (!node) continue;
res.push_back(node->val);
s.push(node->right);
s.push(node->left);
}
return res;
}
};

## # 日期

2017 年 5 月 20 日 2019 年 1 月 25 日 —— 这学期最后一个工作日 2019 年 9 月 20 日 —— 是选择中国互联网式加班？还是外企式养生？