[Leetcode] 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?

后序遍历：左孩子->右孩子->根节点

后序遍历最关键的是利用一个指针保存前一个访问过的信息，避免重复访问。

思路一：

左、右孩子是交叉入栈的，当出栈时，就存在如何从左孩子转向右孩子同时避免重复访问的问题。一个节点值被取出来时，它的左右子节点要么不存在，要么已经被访问过。所以，用head来保存上一个已访问元素的信息，然后判断是否为栈顶元素的左右孩子来实现避免重复访问，至于从左转向右，入栈的顺序已经解决这个问题。原代码

/**

 * 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 *>stk;

        if(root)    stk.push(root);

        TreeNode *head=root;

        while( !stk.empty())

        {

            TreeNode *top=stk.top();

            if(( !top->left&& !top->right)||top->left==head||top->right==head)

            {   //两种情况：一、到达叶节点；二、前一元素是栈顶的左、右孩子即被访问过

                res.push_back(top->val);

                stk.pop();

                head=top;

            }

            else    //结合栈的特点和后边遍历的顺序，右先进

            {

                if(top->right)

                    stk.push(top->right);

                if(top->left)

                    stk.push(top->left);

            }

        }

        return res;

    }

};

思路二：

【后序遍历二叉树的步骤：先遍历二叉树的左子树，再遍历二叉树的右子树，最后访问根结点。非递归实现时，用一个栈模拟遍历过程。由于访问完左子树后访问右子树，栈中元素要起到转向访问其右子树的作用，但是不能像先序和中序遍历那样出栈即可，因为根结点时最后访问的。那么什么时候出栈呢？我们需要一个指针pre来记录前一次访问的结点。如果pre是根结点的右子树，则说明根结点的右子树访问完了，此时根结点就可以出栈了(源代码）】。过程：将左孩子不停的压入栈中，直到由root=root->left得到root为空，然后将栈顶元素的值存入res，用pre记录栈顶元素（在后来可以避免重复访问）。在下次循环中，因，root为空，所以跳过if进入判断else if实现左孩子向右孩子的转变。整体上，左孩子出栈以后，右孩子入栈，用pre记录右孩子，右孩子出栈，利用stk.top()->right !=pre来避免重复访问。

/**

 * 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 *> stk;

        TreeNode *pre=NULL;

        while(root|| !stk.empty())

        {

            if(root)

            {

                stk.push(root);

                root=root->left;

            }

            else if(stk.top()->right !=pre) //判断stk.top()->right是否被访问过

            {

                root=stk.top()->right;

                pre=NULL;

            }

            else

            {

                res.push_back(stk.top()->val);

                pre=stk.top();

                stk.pop();

            }

        }

        return res;

    }

};

思路三：递归版

class Solution {

public:

    vector<int> postorderTraversal(TreeNode *root)

    {

        vector<int> res;

        postOrderTrav(root,res);

        return res;

    }

    void postOrderTrav(TreeNode *root,vector<int> &res)

    {

        if(root==NULL)  return;

        postOrderTrav(root->left,res);

        postOrderTrav(root->right,res);

        res.push_back(root->val);

    }

};

巴特西

[Leetcode] Binary tree postorder traversal二叉树后序遍历

最新文章

热门文章