两种方法:
- 常规方案——正规的后序遍历,关键在于设置空指针
- 利用规律——按照根->右->左的方式访问后,再reverse结果
常规方法
// // Created by jt on 2020/8/8. // #include #include #include using namespace std; /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: /** * * @param root TreeNode类 * @return int整型vector */ vector postorderTraversal(TreeNode *root) { // write code here // 正规解法 // 1.辅助栈 2.关键在于设空指针 vector result; if (!root) return result; stack record; record.push(root); while (!record.empty()) { TreeNode *current = record.top(); if (!current->left && !current->right) { result.push_back(current->val); record.pop(); } else { // 因为访问顺序是先左后右,因此先推入右再推入左 if (current->right) { record.push(current->right); current->right = nullptr; // 设置成空指针,防止再次访问 } if (current->left) { record.push(current->left); current->left = nullptr; } } } return result; } };
利用规律
// // Created by jt on 2020/8/8. // #include #include #include using namespace std; /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: /** * * @param root TreeNode类 * @return int整型vector */ vector postorderTraversal(TreeNode *root) { // write code here // 非正规解法 // 1.辅助栈 2.前序的根->左->右变成根->右->左再reverse vector result; if (!root) return result; stack record; record.push(root); while (!record.empty()) { TreeNode *current = record.top(); record.pop(); result.push_back(current->val); if (current->left) record.push(current->left); if (current->right) record.push(current->right); } reverse(result.begin(), result.end()); return result; } };