[LeetCode] 145. Binary Tree Postorder Traversal

Binary Tree Postorder Traversal

week3

难度：Hard

题目链接

---

题目描述

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. 递归思路：
   递归的做法就是采用分而治之的方法，对一棵树均划分成3个节点，每当到一个节点时，先对其左节点递归，再到右节点，最后插入中节点后结束递归，以及当所到节点为空时也结束递归。

2. 遍历思路：
   遍历的思路就是使用一个栈来存取遍历的节点，当访问完其中所有的子节点时，再使它出栈，其中也是用了递归的思路，因为递归就是通过栈来实现的。

---

代码

1. 递归思路

/**
 * 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> ans;
        if(root == nullptr)
        {
            return ans;
        }
        vector <int> leftans = postorderTraversal(root->left);
        vector <int> rightans = postorderTraversal(root->right);
        ans.insert(ans.end(),leftans.begin(),leftans.end());
        ans.insert(ans.end(),rightans.begin(),rightans.end());
        ans.insert(ans.end(),root->val);
        return ans;
    }
};

2. 遍历思路

/**
 * 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> res;
        if (!root) return res;
        stack<TreeNode*> s;
        s.push(root);
        TreeNode* pre = root;
        while (!s.empty()) {
            TreeNode* p = s.top();
            s.pop();
            res.insert(res.begin(), p->val);
            if (p->left) s.push(p->left);
            if (p->right) s.push(p->right);
        }
        return res;
    }
};

---

Note

按照时间复杂度来算遍历的应该比递归的要快，但在网页上显示是一样的速度，看了一下比较慢的就是一些人先是用了栈来处理节点，到最后访问子节点的时候又用回递归的方法了，这种是典型的没有理解好stack的用法，其先进后出的性质可以让子节点也使用stack来进行遍历。

此外还有一种做法就是使用先序遍历后，再进行翻转从而得到后序遍历的结果。

stack<TreeNode*> stack;
stack.push(root);
while (!stack.empty()) {
    TreeNode* cur = stack.top();
    stack.pop();
    res.push_back(cur->val);
    if (cur->left != nullptr) {
        stack.push(cur->left);
    }
    if (cur->right != nullptr) {
        stack.push(cur->right);
    }
}

reverse(res.begin(),res.end());

return res;