0145._Binary_Tree_Postorder_Traversal.md

145. Binary Tree Postorder Traversal

难度:Hard

刷题内容

原题连接

• https://leetcode.com/problems/binary-tree-postorder-traversal/

内容描述

Given a binary tree, return the postorder traversal of its nodes' values.

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [3,2,1]
Follow up: Recursive solution is trivial, could you do it iteratively?

思路1 - 时间复杂度: O(N)- 空间复杂度: O(1)******

后序遍历二叉树，先判断左子树存不存在，在判断右子树存不存在，最后添加root->val即可。

/**
 * 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:
    void travel(TreeNode* root,vector<int>& v)
    {
        if(!root)
            return;
        if(root ->left)
            travel(root ->left,v);   
        if(root ->right)
            travel(root ->right,v);
        v.push_back(root ->val);
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> v;
        travel(root,v);
        return v;
    }
};

思路2 - 时间复杂度: O(N)- 空间复杂度: O(N)******

题目中提到了不用递归用遍历的方式去解决这个问题。那么我们就需要用栈去储存元素，这时候我们还需要一个辅助栈来标记这个元素是否应该 pop。

/**
 * 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<TreeNode*> v;
        vector<int> ans;
        vector<int> count1;
        if(root)
        {
            v.push_back(root);
            count1.push_back(0);
        }
        while(v.size())
        {
            int index = v.size();
            if(!count1[index - 1] && v[index -1] ->left)
            {
                count1[index - 1] = 1;
                v.push_back(v[index - 1] ->left);
                count1.push_back(0);
            }
            else if(count1[index - 1] != 2 && v[index - 1] ->right)
            {
                count1[index - 1] = 2;
                v.push_back(v[index - 1] ->right);
                count1.push_back(0);
            }
            else
            {
                ans.push_back(v[index - 1] ->val);
                count1.pop_back();
                v.pop_back();
            }
        }
        return ans;
    }
};