15 二叉树的后序遍历（Binary Tree Postorder Traversal）

目录

• ​​1 题目​​
• ​​2 描述​​
• ​3 解决方案​

• ​3.1 递归算法​

• ​3.1.1 遍历法（Traverse）​

• ​​思路​​
• ​​源码​​

• ​3.1.2 分治法（Devide And Conquer）​

• ​3.2 非递归算法​

• ​3.2.1 二叉树遍历的非递归通用解法​

• ​​图解​​

• ​​3.3 时间复杂度​​
• ​​3.4 空间复杂度​​

1 题目

  二叉树的后序遍历（Binary Tree Postorder Traversal）

lintcode：题号——68，难度——easy

2 描述

  给出一棵二叉树，返回其节点值的后序遍历。

名词：

遍历

按照一定的顺序对树中所有节点进行访问的过程叫做树的遍历。

后序遍历

在二叉树中，首先遍历左子树，然后遍历右子树，最后访问根结点，在遍历左右子树时，仍然采用这种规则，这样的遍历方式叫做二叉树的后序遍历。

序列化规则：

使用大括号包裹节点序列来表示二叉树，首个数据为根节点，后面接着是其左儿子和右儿子节点值，"#"表示不存在该子节点，之后以此类推。

样例1：

输入：二叉树 = {1,2,3}

输出：[2,3,1]

解释：上述{1,2,3}序列按照序列化规则表示的二叉树如下

1
    / \
   2   3
      

按照后序遍历规则，先左右子树再根，顺序为[2,3,1]

样例2：

输入：二叉树 = {1,#,2,3}

输出：[1,3,2]

解释：上述{1,#,2,3}序列按照序列化规则表示的二叉树如下

1
      /   \
    #       2
           /
          3
      

按照后序遍历规则，先左右子树再根，顺序为[3,2,1]

3 解决方案

  后序遍历与​​前序遍历​​​​[1]​​、​​中序遍历​​​​[2]​​一样可以使用递归和非递归两类方式，递归和非递归各自的优缺点在前序遍历的介绍中已提过了。

3.1 递归算法

  递归写法比较简单，注意防止死循环，明确递归的三要素。

递归的三要素：

1. 递归的定义（递归函数的返回值、参数要如何定义）
2. 递归的拆解（递归如何向下拆分）
3. 递归的出口（递归的结束条件）

  递归又有两种形式，遍历和分治。

3.1.1 遍历法（Traverse）

思路

  遍历的整个过程可以看成是为了完成某项大任务，于是领导亲自下基层处理各项小任务，所有工作都“亲历亲为”，参与了所有工作最终完成了大任务。

遍历法的主要递归函数一般不带返回值，会拥有​

​全局参数​

​或者贯穿整个递归过程的​

​函数参数​

​用来处理数据。

源码

  C++版本：

/**
* @param root: A Tree
* @return: Postorder in ArrayList which contains node values.
*/
vector<int> postorderTraversal(TreeNode * root) {
    // write your code here
    vector<int> result;
    traverse(root, result);
    return result;
}

// 遍历法的递归函数，没有返回值，函数参数result贯穿整个递归过程用来记录遍历的结果
void traverse(TreeNode * root, vector<int> & result) // 递归三要素之定义
{
    if (root == nullptr)
    {
        return; // 递归三要素之出口
    }

    // 前、中、后序三种遍历在此处对子树与根节点的处理顺序不同，后续遍历先处理左子树，再处理右子树，最后处理根节点
    traverse(root->left, result); // 递归三要素之拆解
    traverse(root->right, result);
    result.push_back(root->val);
}
      

3.1.2 分治法（Devide And Conquer）

  分治法的整个过程可以看成是为了完成某项大人物，于是领导把各项工作分派给各个下属，各个下属又把工作继续细分层层向下分派给基层人员，每一级都只需要获取下级完成的任务结果即可，最终所有层级任务都完成了，大任务也对应完成了。

分治法的主要递归函数一般需要有返回值，用来向上一层提供结果。

/**
* @param root: A Tree
* @return: Postorder in ArrayList which contains node values.
*/
// 由于主函数的形式已经符合分治法需要的形式（具有合适的返回值），直接使用主函数做为递归函数
vector<int> postorderTraversal(TreeNode * root) {
    // write your code here
    vector<int> result;
    if (root == nullptr)
    {
        return result; // 递归三要素之出口
    }

    // 获取左子树的遍历结果
    vector<int> leftResult = postorderTraversal(root->left); // 递归三要素之拆解
    // 获取右子树的遍历结果
    vector<int> rightResult = postorderTraversal(root->right);

    // 前、中、后序三种遍历在此处对子树与根节点的处理顺序不同，后续遍历先处理左子树，再处理右子树，最后处理根节点
    result.insert(result.end(), leftResult.begin(), leftResult.end());
    result.insert(result.end(), rightResult.begin(), rightResult.end());
    result.push_back(root->val);

    return result;
}
      

3.2 非递归算法

3.2.1 二叉树遍历的非递归通用解法

  在后序遍历的非递归算法中，采用针对二叉树的前、中、后序遍历都比较通用的形式来解决遍历问题，在该通用解法中，后序遍历与​​前序遍历​​​​[1:1]​​、​​中序遍历​​​​[2:1]​​的不同之处在于对节点的解析操作发生的时刻与处理方式，前序遍历是“边入栈边解析”，中序遍历是“出栈时解析”，后序遍历则是“出栈时判断条件解析”。

1. 左穿入栈到底；
2. 从栈内弹出当前节点，可能是​

   ​左子树​

   ​或者​

   ​根节点​

   ​（相对），出栈时判断解析；（前序遍历是在入栈时解析，中序是弹出时解析，后序是弹出时判断条件解析）

判断条件为：下一步是否需要解析右子树？

需要解析右子树：右子树非空且未被解析；(cur->right != nullptr && prev != cur->right)

不需要解析右子树：右子树为空或已经被解析过。

1. ​

   ​右子树​

   ​的根节点入栈，重复1、2步骤（即对右子树做中序遍历），直到满足循环结束条件，该二叉树的后序遍历即在结果序列中。

后序遍历的初始条件和循环结束条件在通用解法中与前、中序遍历一致。

初始条件：​

​栈为空​

​、​

​当前指针指向根节点​

​。

循环结束条件：​

​栈为空​

​且​

​当前指针为空​

后序遍历为了判断右子树是否已经被解析过，需要额外使用一个指针​

​prev​

​来记录上一个解析过的节点。

/**
* @param root: A Tree
* @return: Postorder in ArrayList which contains node values.
*/
vector<int> postorderTraversal(TreeNode * root) {
    // write your code here
    vector<int> result;
    if (root == nullptr)
    {
        return result;
    }

    stack<TreeNode *> nodeStack;
    TreeNode * prev = nullptr; // prev用来记录上一个解析过的节点
    TreeNode * cur = root;
    while (cur != nullptr || !nodeStack.empty())
    {
        while (cur != nullptr)
        {
            nodeStack.push(cur);
            cur = cur->left;
        }

        cur = nodeStack.top();
        // 此处是后序遍历不同的地方，出栈时判断条件解析
        if (cur->right != nullptr && prev != cur->right) // 右子树存在且未被解析
        {
            cur = cur->right; // 右节点成为下一个要处理的节点
        }
        else // 右子树为空或者右子树已经被解析过了
        {
            result.push_back(cur->val);
            nodeStack.pop();
            // 后序遍历在此处比前、中序遍历多了两行
            prev = cur; // 使用prev记录解析过的节点
            cur = nullptr; // 将cur至空，防止重复解析存在右子树的节点
        }
    }

    return result;
}
      

图解

  在逻辑上，前、中、后序遍历的过程大致相同，可以参考​​前序遍历​​​​[1:2]​​的图解，区别只是解析操作发生的时刻和处理方式不同。

3.3 时间复杂度

  对二叉树的遍历，不管使用什么方式都是将整棵树中的所有节点走一遍，所以算法的时间复杂度都为O(n)。

  关于二叉树和分治法的时间复杂度的更多内容，在​​前序遍历​​​​[1:3]​​中已经进行了计算分析。

3.4 空间复杂度

  算法的空间复杂度，分治法为O(n)，上述其余方法都为O(1)。

1. 二叉树的前序遍历：javascript:void(0) ↩︎ ↩︎ ↩︎ ↩︎
2. 二叉树的中序遍历：javascript:void(0) ↩︎ ↩︎