[leetcode]binary-tree-postorder-Traversal

- 日理万妓 2022-03-20 20:39 131阅读 0赞

## 题目描述： ##

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

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

## 实现思路： ##

要实现非递归的二叉树后序遍历，这里学习到了一个巧妙的解法，借助栈来实现，将前序遍历加以修改：前序遍历是根-左-右，这里将顺序改成根-右-左，然后reverse一下，就变成左-右-根即后序遍历的顺序了~

## 具体实现： ##

/**
     * 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;
            if(!root){
                return res;
            }
            stack<TreeNode *> st;
            st.push(root);
            while(st.size()){
                TreeNode* temp;
                temp = st.top();
                st.pop();
                res.push_back(temp->val);
                if(temp->left){
                    st.push(temp->left);
                }
                if(temp->right){
                    st.push(temp->right);
                }
            }
            reverse(res.begin(), res.end());
            return res;
        }
    };

[leetcode]binary-tree-postorder-Traversal

发表评论取消回复

还没有评论，来说两句吧...

相关阅读