LeetCode 145 二叉树的后序遍历（非递归）

题目：

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

示例:

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

   1

    \

     2

    /

   3 

输出: [3,2,1]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

解题思路：

1、使用一个栈，先把二叉树的右孩子压入，再把左孩子压入。这样在输出时就满足后序要求（先左后右）。

2、当某个节点的左孩子或者右孩子都为NULL时，可以访问。此外记录当前节点p的上一个节点last，因为当p的左右孩子都已访问过时，轮到p被访问，设置last可标志p的左右孩子是否都被访问过了。即为 if((p->right == NULL && p->left == last) || p->right == last)

代码：

 /**

  * 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) {

         vector<int> ans;

         if(root == NULL)

             return ans;

         TreeNode* p = root;

         TreeNode* last;

         stack<TreeNode*> s;

         s.push(p);

         while(!s.empty())

         {

             p = s.top();

             if((p->left == NULL && p->right == NULL) || (p->right == NULL && p->left == last) || p->right == last)

             {

                 ans.push_back(p->val);

                 last = p;

                 s.pop();

             }

             else

             {

                 if(p->right)

                     s.push(p->right);

                 if(p->left)

                     s.push(p->left);

             }

         }

         return ans;

     }

 };

巴特西

LeetCode 145 二叉树的后序遍历（非递归）

最新文章

热门文章