二叉树的后序遍历

约定不等于承诺〃 2022-10-22 04:08 169阅读 0赞

**二叉树文章系列：**

1.  [二叉树的前序遍历][Link 1]
2.  [二叉树的中序遍历][Link 2]
3.  [二叉树的后序遍历][Link 3]
4.  [二叉树的层序遍历][Link 4]
5.  [二叉树的前序、中序、后序、层序遍历【解法完整版】][Link 5]

### 本文目录 ###

*   *  一、解题思路：递归
     *  二、解题思路：迭代（方法1）
     *  三、解题思路：迭代（方法2）
     *  四、解题思路：迭代（方法3）

![3f6957d485721213ec35be97bbe89d42.png][]

二叉树的后序遍历的记忆法则是“左右根"，即先遍历左子树节点，再遍历右子树节点，最后遍历根节点。

以上图为例，后序遍历的结果是【D, E, B, F, G, C, A】

## 一、解题思路：递归 ##

递归是我们实现前中后序遍历最常用的方法。

> 什么问题可以采用递归求解呢？
> 
> 需要满足三个条件：
> 
> 1.  一个问题的解可以分解为若干个子问题的解；
> 2.  这个问题与分解的子问题，除了数据规模不同外，求解思路相同
> 3.  存在递归终止条件。
> 
> 那么在知道一个问题可以采用递归实现之后，如何写出递归代码呢？
> 
> 关键在于**能写出递归公式，找到终止条件。**

在二叉树的前序遍历问题上，它的递归公式是:

> preorder(node) = preorder(node->left) --> preorder(node->right) —> print node

它的终止条件是：

> node 是否为空，为空则返回。

class Solution {
    public:
        vector<int> preorderTraversal(TreeNode* root) {
            vector<int> res;
            preorder(res, root);
            return res;
        }
    
        void preorder(vector<int>& res, TreeNode* root){
            
            if(!root) return;
            res.emplace_back(root->val);
            preorder(res, root->left);
            preorder(res, root->right);
        }
    };

## 二、解题思路：迭代（方法1） ##

我们在使用迭代法来实现后序遍历的时候，通常有两大类思路。**第一类是先得到“根右左”，然后对输出列表反序，即得到“左右根”； 第二类是直接求出“左右根”。**

咱们知道，前序遍历是求“根左右”，那么我们可以使用前序遍历的方法，去求得“根右左”。以上图为例，我们求得的“根右左”的结果是【A, C, G, F, B, E, D】。再对这个结果反序，得到【D, E, B, F, G, C, A】。这正是咱们想得到的后序遍历。

本文第二节和第三节介绍的两种迭代方法，都是采用这种思路来实现。最后第四小节，我们会介绍直接求出后序遍历的思路。

--------------------

在递归方法实现过程中，它的底层是基于系统栈的结构来实现的。因此，我们可以使用栈的数据结构来辅助实现基于迭代方式的后序遍历。

具体思路为：

*  初始化栈stack，初始化输出列表res
 *  根节点入栈
 *  while(栈不为空)，在循环体内部：
    
     *  栈顶元素出栈
     *  栈顶元素添加到输出列表
     *  如果栈顶元素的左子树节点不为空，将左子树节点入栈
     *  如果栈顶元素的右子树节点不为空，将右子树节点入栈
 *  对输出列表res 进行反序
 *  返回输出列表res

![df0ebbbe290efcf620f37dfc3ace397e.png][]

class Solution {
    public:
        vector<int> postorderTraversal(TreeNode* root) {
    
            vector<int> res;
            if(!root) return res;
    
            stack<TreeNode*> s;
            s.push(root);
            while(!s.empty()){
                TreeNode* node = s.top();
                s.pop();
                res.emplace_back(node->val);
                if(node->left) s.push(node->left);
                if(node->right) s.push(node->right);
            }
            reverse(res.begin(), res.end());
            return res;
        }
    };

## 三、解题思路：迭代（方法2） ##

基于迭代方法的第二种思路如下：

*  初始化栈stack，初始化输出列表res
 *  设置一个变量cur, 表示当前节点。并赋初始值为根节点root
 *  while(栈不为空 或者 当前节点cur不为空)，在循环体内部：
    
     *  沿着当前节点的右分支一直走，直到为空。在这个过程中将遍历的节点都入栈，同时添加到输出列表
     *  栈顶元素出栈
     *  更新当前节点cur为栈顶元素的左子树节点。
 *  对输出列表res 进行反序
 *  返回输出列表res

以图中的二叉树为例，来一步步来展示这个过程：

![3f6957d485721213ec35be97bbe89d42.png][]

初始时，当前节点cur = root ，即节点A

![c2c3c6ba7b3ceea25402754be2cd5b99.png][]

![图片3][3]

![图片4][4]

![图片5][5]

![图片6][6]

![图片7][7]

![图片8][8]

class Solution {
    public:
        vector<int> postorderTraversal(TreeNode* root) {
    
            vector<int> res;
            if(!root) return res;
    
            stack<TreeNode*> s;
            TreeNode* cur = root;
            while(!s.empty() || cur){
                while(cur){
                    res.emplace_back(cur->val);
                    s.push(cur);
                    cur = cur->right;
                }
                TreeNode* node = s.top();
                s.pop();
                cur = node->left;
            }
            reverse(res.begin(), res.end());
            return res;
        }
    };

## 四、解题思路：迭代（方法3） ##

这次我们要尝试直接得到后序遍历的结果。

我们知道后序遍历的顺序是”左右根“。那么对于一个根节点，要先遍历它的左子树节点和右子树节点，再回头遍历根节点。

为了防止遍历根节点的时候，再次遍历到它的左、右子树节点；我们需要一个变量，来表示最后一次出栈的元素。

class Solution {
    public:
        vector<int> postorderTraversal(TreeNode* root) {
    
            vector<int> res;
            if(!root) return res;
    
            stack<TreeNode* > s;
            s.push(root);
            TreeNode* lastPopNode = root;
            while(!s.empty()){
                TreeNode* node = s.top();
                if(node->left && node->left != lastPopNode && node->right != lastPopNode){
                    s.push(node->left);
                }else if(node->right && node->right != lastPopNode){
                    s.push(node->right);
                }else{
                    res.emplace_back(node->val);
                    s.pop();
                    lastPopNode = node;
                }
            }
            return res;  
        }
    };

[Link 1]: https://blog.csdn.net/u010414589/article/details/115415226
[Link 2]: https://blog.csdn.net/u010414589/article/details/115415373
[Link 3]: https://blog.csdn.net/u010414589/article/details/115415388
[Link 4]: https://blog.csdn.net/u010414589/article/details/114905914
[Link 5]: https://blog.csdn.net/u010414589/article/details/115415401
[3f6957d485721213ec35be97bbe89d42.png]: /images/20221022/157680770f8a4a65a1172a37cadc275b.png
[df0ebbbe290efcf620f37dfc3ace397e.png]: /images/20221022/b273c72517814860b44ee0114e67b5a5.png
[c2c3c6ba7b3ceea25402754be2cd5b99.png]: /images/20221022/e17cbc2803394866b9c485f94938c9b5.png
[3]: /images/20221022/e8be9ea0985845de8afeb1fa1caf0f59.png
[4]: /images/20221022/1ee66bbb28a1429ebac54bae46b23379.png
[5]: /images/20221022/bac9f48af4b14b2190de06e2dee3a053.png
[6]: /images/20221022/957f2bcddd3d426db8b0a6012e76c195.png
[7]: /images/20221022/4dc295e3475947139dbf8dd1bf313a89.png
[8]: /images/20221022/08d73e7ba2614d918238f36b8402cf2f.png