Binary Tree Preorder Traversal.png
解題思路 ：
Recursive 方式：
pre-order 基本做法三步驟
- statements;
- recursive call (left)
- recursive call (right)
這邊的 statement 就是把數值存到要回傳的 vector 裡面 當然只處理不是 nullptr 的節點 所以要設定一個 if statement 來檢查
Non - Recursive 方式：
可以使用 stack 只是放入 stack 的順序是 先 right child 然後才放 left child (倒出來才會是正確順序)
C++ code :
<pre><code>
//Recursive:
void preOrder(TreeNode *root, vector<int> &res)
{
if(root != nullptr){
res.emplace_back(root->val);
preOrder(root->left, res);
preOrder(root->right, res);
}
}
class Solution {
public:
/**
* @param root: The root of binary tree.
* @return: Preorder in vector which contains node values.
*/
vector<int> preorderTraversal(TreeNode *root) {
// write your code here
vector<int> res;
preOrder(root, res);
return res;
}
};
<code><pre>
//Non - Recursive
class Solution {
public:
/**
* @param root: The root of binary tree.
* @return: Preorder in vector which contains node values.
*/
vector<int> preorderTraversal(TreeNode *root) {
// write your code here
vector<int> res;
if(root == nullptr) return res;
stack<TreeNode*> s;
s.push(root);
while(!s.empty())
{
TreeNode *tmp = s.top();
s.pop();
res.emplace_back(tmp->val);
if(tmp->right) s.push(tmp->right);
if(tmp->left) s.push(tmp->left);
}
return res;
}
};
