青岛做外贸网站建设搜索网站大全

• 二叉树的后序遍历，指首先遍历二叉树的左节点，然后遍历二叉树的右节点，最后遍历中间节点。按照顺序进行递归遍历即可。

/*** 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:void traversal(TreeNode* cur, vector<int>& vec){if(cur == nullptr){return;}traversal(cur->left, vec);traversal(cur->right, vec);vec.push_back(cur->val);}vector<int> postorderTraversal(TreeNode* root) {vector<int> result;traversal(root, result);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> postorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;TreeNode* cur = root;st.push(root);while(cur!= nullptr && !st.empty()){cur = st.top();st.pop();result.push_back(cur->val);if(cur->left != nullptr){st.push(cur->left);}if(cur->right != nullptr){st.push(cur->right);}}reverse(result.begin(), result.end());return result;      }
};