【LeetCode】Binary Tree Postorder Traversal(二叉树的后序遍历)

这道题是LeetCode里的第145道题。

题目要求：

给定一个二叉树，返回它的后序遍历。

示例:
输入: [1,null,2,3]

   1

    \

     2

    /

   3 

输出: [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) {

        stack<TreeNode*>st;

        TreeNode *cur,*pre=NULL;

        vector<int>res;

        if(root==NULL)

            return res;

        cur=root;

        st.push(cur);

        while(st.size()!=0){

            cur=st.top();

            if((cur->left==NULL&&cur->right==NULL)||

              (pre!=NULL&&(pre==cur->left||pre==cur->right))

              ){

                res.push_back(cur->val);

                st.pop();

                pre=cur;

            }

            else{

                if(cur->right!=NULL)

                    st.push(cur->right);

                if(cur->left!=NULL)

                    st.push(cur->left);

            }

        }

        return res;

    }

};

提交结果：

个人总结：

后序遍历迭代法比较难，同样还是先左后右，和前序遍历、中序遍历一起对照着学习进行总结会更好一点。

巴特西

【LeetCode】Binary Tree Postorder Traversal(二叉树的后序遍历)

这道题是LeetCode里的第145道题。

题目要求：

解题代码：

提交结果：

个人总结：

最新文章

热门文章