【144】二叉樹的前序遍歷

1、遞歸法：

class Solution {
public:void preorder(TreeNode* root, vector<int> &res){if(root == nullptr){return;}res.push_back(root->val);preorder(root->left, res);preorder(root->right, res);}vector<int> preorderTraversal(TreeNode* root) {vector<int> res;preorder(root, res);return res;}
};

2、迭代法

?

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

【94】二叉樹的中序遍歷

1、遞歸法

class Solution {
public:void postorder(TreeNode* root, vector<int>& res){if(root == nullptr){return;}postorder(root->left, res);res.push_back(root->val);postorder(root->right, res);}vector<int> inorderTraversal(TreeNode* root) {vector<int> res;postorder(root, res);return res;}
};

2、迭代法?

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> res;if(root == nullptr){return res;}stack<TreeNode*> stk;TreeNode* node = root;while(!stk.empty() || node != nullptr){while(node != nullptr){stk.push(node);node = node->left;}node = stk.top();res.push_back(node->val);stk.pop();node = node->right;}return res;}
};

復雜度分析：

時間復雜度：O（N）每個結點會遍歷一次且只遍歷一次?

空間復雜度：O（N）棧至多會存放所有樹節點

【145】二叉樹的后序遍歷

1、遞歸法

class Solution {
public:void postorder(TreeNode* root, vector<int>& res){if(root == nullptr){return;}postorder(root->left, res);postorder(root->right, res);res.push_back(root->val);}vector<int> postorderTraversal(TreeNode* root) {vector<int> res;postorder(root, res);return res;}
};

2、迭代法?

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

思路：

從根節點開始遍歷，并將根節點入棧，再遍歷他的左子樹，并依次入棧，直到該結點沒有左子樹。判斷這個結點是否有右子樹，如果沒有，則將該結點彈出棧，并記錄結點值。如果有則繼續從他的右子樹進行遍歷，同時記錄該結點的右子樹是否遍歷過，如果遍歷過，則彈棧并記錄結點值。?