LeetCode刷题笔记（树）：binary-tree-postorder-traversal

怼烎@ 2022-05-31 04:29 171阅读 0赞

--------------------

*  **转载请注明作者和出处：[http://blog.csdn.net/u011475210][http_blog.csdn.net_u011475210]**
 *  **代码地址：[https://github.com/WordZzzz/Note/tree/master/LeetCode][https_github.com_WordZzzz_Note_tree_master_LeetCode]**
 *  **刷题平台：[https://www.nowcoder.com/ta/leetcode][https_www.nowcoder.com_ta_leetcode]**
 *  **题  库：Leetcode经典编程题**
 *  **编  者：WordZzzz**

--------------------

*   *  题目描述
     *  解题思路
     *  C版代码实现
        
         *  递归
         *  迭代

## 题目描述 ##

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

For example:  
Given binary tree\{1,\#,2,3\},

1  
\\  
2  
/  
3

return\[3,2,1\].

Note: Recursive solution is trivial, could you do it iteratively?

给定一个二叉树，返回其节点值的后序遍历。

注意：递归解决方案是微不足道的，你可以迭代地做？

## 解题思路 ##

两种方法，递归和迭代，递归太简单了，直接贴出代码就不多说了。

后序遍历的非递归版可以说是三种遍历中最难的了，因为要先穷举左右结点，最后才是根结点。在外循环中，第一步还是依次将左子树入栈；然后看栈顶元素，如果栈顶元素没有右孩子，或者右孩子时候已经遍历过，那么就弹出栈顶元素，并记录；否则，遍历右子树。

## C++版代码实现 ##

### 递归 ###

/**
     * Definition for binary tree
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
    
        void postorder(TreeNode *root, vector<int> &res){
            if(root){
                postorder(root->left, res);
                postorder(root->right, res);
                res.push_back(root->val);
            }
        }
    
        vector<int> postorderTraversal(TreeNode *root) {
            vector<int> res;
            postorder(root, res);
            return res;
        }
    };

### 迭代 ###

/**
     * Definition for binary tree
     * 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;
            stack<TreeNode *> sta;
            TreeNode *cur = root, *last = NULL;
            while(cur != NULL || !sta.empty()){
                while(cur != NULL){
                    sta.push(cur);
                    cur = cur->left;
                }
                cur = sta.top();
                if(cur->right == NULL || cur->right == last){
                    sta.pop();
                    res.push_back(cur->val);
                    last = cur;
                    cur = NULL;
                }else
                    cur = cur->right;
            }
            return res;
        }
    };

**系列教程持续发布中，欢迎订阅、关注、收藏、评论、点赞哦～～(￣▽￣～)～**

**完的汪(∪｡∪)｡｡｡zzz**

[http_blog.csdn.net_u011475210]: http://blog.csdn.net/u011475210
[https_github.com_WordZzzz_Note_tree_master_LeetCode]: https://github.com/WordZzzz/Note/tree/master/LeetCode
[https_www.nowcoder.com_ta_leetcode]: https://www.nowcoder.com/ta/leetcode