# 144. 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?

1. 把根节点 push 到栈中

2. 循环检测栈是否为空，若不空，则取出栈顶元素，保存其值，然后看其右子节点是否存在，若存在则 push 到栈中。再看其左子节点，若存在，则 push 到栈中。

``````class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
if (!root) return {};
vector<int> res;
stack<TreeNode*> s{{root}};
while (!s.empty()) {
TreeNode *t = s.top(); s.pop();
res.push_back(t->val);
if (t->right) s.push(t->right);
if (t->left) s.push(t->left);
}
return res;
}
};
``````

``````class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> st;
TreeNode *p = root;
while (!st.empty() || p) {
if (p) {
st.push(p);
res.push_back(p->val);
p = p->left;
} else {
p = st.top(); st.pop();
p = p->right;
}
}
return res;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/144

Binary Tree Inorder Traversal

Binary Tree Postorder Traversal

Binary Tree Level Order Traversal

Verify Preorder Sequence in Binary Search Tree

Verify Preorder Serialization of a Binary Tree

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

https://leetcode.com/problems/binary-tree-preorder-traversal/discuss/45468/3-Different-Solutions

https://leetcode.com/problems/binary-tree-preorder-traversal/discuss/45493/Accepted-code.-Explaination-with-Algo.

https://leetcode.com/problems/binary-tree-preorder-traversal/discuss/45266/Accepted-iterative-solution-in-Java-using-stack.

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation