145. Binary Tree Postorder Traversal

 

QuestionEditorial Solution

 

 

• Total Accepted: 106482
• Total Submissions: 291244
• Difficulty: Hard

 

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

For example:

Given binary tree {1,#,2,3},

1    \     2    /   3

 

return [3,2,1].

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

 

 to see which companies asked this question

Hide Tags

 

 

Show Similar Problems

 

 

题解转自：

 

分析如下：

a)普通的做法

题目要求对二叉树进行非递归的后序遍历，所谓后序遍历即，先访问左子树、然后是右子树，最后访问根节点。通常采用递归的方法，题目要求采用非递归的方法实现。算法如下：

1）如果根节点非空，将根节点加入到栈中。

2）如果栈不空，取栈顶元素（暂时不弹出），

                             如果（左子树已访问过或者左子树为空），且（右子树已访问过或右子树为空），则弹出栈顶节点，将其值加入数组，

                            如果左子树不为空，切未访问过，则将左子节点加入栈中，并标左子树已访问过。

                            如果右子树不为空，切未访问过，则将右子节点加入栈中，并标右子树已访问过。

3）重复第二步，直到栈空。

 

 

b) 优雅的做法

这是二叉树的后序遍历，题目要求用非递归。写过，依稀有些印象，这次自己写了写，还是没写成功。前序后序中序遍历都会用到栈这个结构，这也是由树这种数据结构的特点决定的。比较特殊的是，后序遍历的顺序是"左子树->右子树->根"，它要求左子树和右子树都在根之前输出。根据这个特点，可以这样来进行，每次记录一个pre和cur，cur表示当前节点，pre表示上次输出的节点(是上次输出的节点，不是上次访问的节点)，如果pre正好是cur的左子树或者右子树，那么就可以输出cur，否则，说明还有cur的左子树或者右子树等待输出，也就是还没到cur输出的时候。这是第一个可以让cur输出的条件。另外可以可以让cur输出的条件是，cur是叶子节。

 

 

1 /** 2  * Definition for a binary tree node. 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 class Solution {11 public:12     vector
      
        postorderTraversal(TreeNode* root) {13         vector
       
         ans;14         TreeNode* pre = root;15         TreeNode* cur = NULL;16         if(root == NULL) return ans;17         stack
        
          s;18         s.push(root);19         while(s.size() >= 1) {20             cur = s.top();21             //如果cur是叶子节点，输出。或者如果pre正好是cur的左子树或者右子树，那么就可以输出cur，否则，说明还有cur的左子树或者右子树等待输出，也就是还没到cur输出的时候。22             //printf(" size = %d cur = %d\n",s.size(),cur->val);23             if( (cur->left == NULL && cur->right == NULL) || (pre == cur->left || pre == cur->right) ) {24                 pre = cur;25                 ans.push_back(cur->val);26                 s.pop();27             }28             else{29                 if(cur->right != NULL) {30                     s.push(cur->right);31                 }32                 if(cur->left != NULL) {33                     s.push(cur->left);34                 }35             }36         }37         return ans;38     }39 };