企业网站开发实训心得_生成网站有吗免费的_谷歌搜索引擎在线_公司网页网站建设

前序遍历

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

后序遍历
这里的思路是交换了

			st.push(node->right);st.push(node->left);

的顺序，从先序列遍历的根左右变成了根右左，接着通过reverse变成了左右根，即后序遍历。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;st.push(root);while(!st.empty()) {TreeNode* node = st.top();st.pop();if(node != nullptr) result.push_back(node->val);else continue;st.push(node->left);st.push(node->right);}reverse(result.begin(), result.end());return result;}
};

中序遍历
写法一：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;TreeNode* cur = root;while (cur != nullptr || !st.empty()) {if(cur != nullptr) {st.push(cur);cur = cur->left;} else {cur = st.top();st.pop();result.push_back(cur->val);cur = cur->right;}}return result;}
};

写法二：

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;TreeNode* node = root;while (node || !st.empty()) {  // 遍历整个树while (node) {             // 先遍历到最左st.push(node);node = node->left;}node = st.top();st.pop();result.push_back(node->val);node = node->right;  // 进入右子树}return result;}
};