[LeetCode] 145. 二叉树的后序遍历

[Animenzzzz]

题目描述：

给定一个二叉树，返回它的 后序 遍历。

示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [3,2,1]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

解题思路：使用栈后序遍历，左-右-根。其中head节点是为了记录上一个处理过的节点，因为是后序遍历，所以node会是根节点，head为其叶子节点

C++解题：

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if(!root) return {};
        vector<int> result;
        stack<TreeNode *> ss;
        TreeNode* head = root;
        ss.push(root);
        while (!ss.empty())
        {
            TreeNode* node = ss.top();
            if ((!node->left && !node->right) || node->left == head || node->right == head)
            {
                result.push_back(node->val);
                ss.pop();
                head = node;
            }else{
                if(node->right) ss.push(node->right);
                if(node->left) ss.push(node->left);
            }
        }
        return result;
    }
};