?LeetCode刷題實(shí)戰(zhàn)145：二叉樹的后序遍歷

/**
?* Definition for a binary tree node.
?* struct TreeNode {
?* int val;
?* TreeNode *left;
?* TreeNode *right;
?* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
?* };
?*/
class?Solution?{
public:
??vector<int> postorderTraversal(TreeNode* root) {
????vector<int> result;
????set visited;//用于標(biāo)記已經(jīng)訪問過的節(jié)點(diǎn)
????stack myStack;//輔助棧，用于保留現(xiàn)場(chǎng)
????while?(root != NULL?|| !myStack.empty()) {
??????if?(root != NULL) {
????????myStack.push(root);//棧先保護(hù)根節(jié)點(diǎn)的現(xiàn)場(chǎng)
????????visited.insert(root);//標(biāo)記根節(jié)點(diǎn)已訪問
????????if?(root->right) {//右子樹不為空，保護(hù)右子樹現(xiàn)場(chǎng)
??????????myStack.push(root->right);
????????}
????????root = root->left;//現(xiàn)場(chǎng)轉(zhuǎn)移至左子樹
????????continue;
??????}
??????root = myStack.top();//恢復(fù)現(xiàn)場(chǎng)
??????myStack.pop();
??????while?(visited.find(root) != visited.end()) {//如果這個(gè)節(jié)點(diǎn)已經(jīng)訪問過(根節(jié)點(diǎn))
????????result.push_back(root->val);
????????if?(!myStack.empty()) {
??????????root = myStack.top();//再恢復(fù)現(xiàn)場(chǎng)
??????????myStack.pop();
????????}
????????else?{
??????????root == NULL;
????????????????????return?result;
????????}
??????}
????}
????return?result;
??}
};