北京做校园的网站,app购物商城,网络信息公司是做什么的,wordpress防淘宝主题二叉树的后序遍历#xff0c;指首先遍历二叉树的左节点#xff0c;然后遍历二叉树的右节点#xff0c;最后遍历中间节点。按照顺序进行递归遍历即可。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *rig…二叉树的后序遍历指首先遍历二叉树的左节点然后遍历二叉树的右节点最后遍历中间节点。按照顺序进行递归遍历即可。
/*** 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, vectorint vec){if(cur nullptr){return;}traversal(cur-left, vec);traversal(cur-right, vec);vec.push_back(cur-val);}vectorint postorderTraversal(TreeNode* root) {vectorint 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:vectorint postorderTraversal(TreeNode* root) {vectorint result;stackTreeNode* 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; }
};
