LeetCode145：Binary Tree Postorder Traversal

题目：

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

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

return [3,2,1].

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

解题思路：

后序遍历的非递归实现与前序遍历和中序遍历的非递归不同，对于根节点，必须当其右孩子都访问完毕后才能访问，所以当根节点出栈时，要根据标志位判断是否为第一次出栈，如果是，则将其标志位置为FALSE，然后再次入栈，先访问其右孩子，当某个节点出栈时且其标志位为false，说明该节点为第二次出栈，即表示其右孩子都已处理完毕，可以访问当前节点了

实现代码：

#include <iostream>

#include <vector>

#include <stack>

using namespace std;

/**

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

*/

struct TreeNode {

     int val;

     TreeNode *left;

     TreeNode *right;

     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

void addNode(TreeNode* &root, int val)

{

    if(root == NULL)

    {

        TreeNode *node = new TreeNode(val);

        root = node;

    }

    else if(root->val < val)

    {

        addNode(root->right, val);

    }

    else if(root->val > val)

    {

        addNode(root->left, val);

    }

}

void printTree(TreeNode *root)

{

    if(root)

    {

        cout<<root->val<<" ";

        printTree(root->left);

        printTree(root->right);

    }

}

struct Node

{

    TreeNode *treeNode;

    bool isFirst;

};

class Solution {

public:

    vector<int> postorderTraversal(TreeNode *root) {

        vector<int> ivec;

        if(root)

        {

            stack<Node*> istack;

            TreeNode *p = root;

            while(!istack.empty() || p)

            {

                while(p)

                {

                    Node *tmpNode = new Node();

                    tmpNode->treeNode = p;

                    tmpNode->isFirst = true;

                    istack.push(tmpNode);

                    p = p->left;

                }

                if(!istack.empty())

                {

                    Node *node = istack.top();

                    istack.pop();

                    if(node->isFirst)//第一次出栈，

                    {

                        node->isFirst = false;

                        istack.push(node);

                        p = node->treeNode->right;

                    }

                    else//表示其右孩子都已经访问了，可以访问当前节点了

                    {

                        ivec.push_back(node->treeNode->val);

                    }

                }

            }

        }

        return ivec;

    }

};

int main(void)

{

    TreeNode *root = new TreeNode();

    addNode(root, );

    addNode(root, );

    addNode(root, );

    addNode(root, );

    printTree(root);

    cout<<endl;

    Solution solution;

    vector<int> v = solution.postorderTraversal(root);

    vector<int>::iterator iter;

    for(iter = v.begin(); iter != v.end(); ++iter)

        cout<<*iter<<" ";

    cout<<endl;

    return ;

}

巴特西

LeetCode145：Binary Tree Postorder Traversal

最新文章

热门文章