</pre>第一種最常用的就是直接暴力遞歸的方法:<p></p><p></p><pre name="code" class="cpp">/**
* 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) {
// write your code here
vector<int> result;
if(root){
trav_pre(root, result);
}
return result;
}
private:
void trav_pre(TreeNode *x, vector<int> &ret) {
if (x == nullptr){
return;
}
ret.push_back(x -> val);
trav_pre(x -> left, ret);
trav_pre(x -> right, ret);
}
};
第二種是使用分而治之的方法:
這種方法在現實中比較常用,相當于本身前序周遊,就是為了實作一個接口,這樣通過不斷調用本接口來解決問題。
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> result;
if (root == nullptr) {
return result;
}
//devide
vector<int> left = preorderTraversal(root -> left);
vector<int> right = preorderTraversal(root -> right);
//conquer
result.push_back(root -> val);
result.insert(result.end(), left.begin(), left.end());
result.insert(result.end(), right.begin(), right.end());
return result;
}
};
第三種是使用非遞歸的方法:
這個方法的關鍵就是引入棧,用棧來代替遞歸的思想
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> result;
stack<TreeNode *> sta;
while(1){
travel_pre(root, result, sta);
if(sta.empty()){
break;
}
root = sta.top();
sta.pop();
}
return result;
}
private:
void travel_pre(TreeNode *x, vector<int> &ret, stack<TreeNode *> &st) {
while (x){
ret.push_back(x -> val);
st.push(x -> right);
x = x -> left;
}
return;
}
};
不用遞歸的另外一種寫法:
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> result;
stack<TreeNode *> sta;
if (root == nullptr){
return result;
}
sta.push(root);
while(!sta.empty()) {
TreeNode * tem = sta.top();
result.push_back(tem -> val);
sta.pop();
if (tem -> right) {//因為是前序周遊,棧是先進後出,是以先放右邊再放左邊
sta.push(tem -> right);
}
if (tem -> left) {
sta.push(tem -> left);
}
}
return result;
}
};