145.二叉树的后序遍历

题目描述

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

示例:

1
2
3
4
5
6
7
8
输入: [1,null,2,3]  
1
\
2
/
3

输出: [3,2,1]

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

题解

算法描述

  • 递归
  • 迭代

思路

这里主要说一下迭代法:

  1. 先序遍历的顺序:左孩子 -> 右孩子 -> 根节点;
  2. 我们可以与先序遍历对比一下:
    • 先序遍历的顺序:根节点 -> 左孩子 -> 右孩子
    • 先序遍历的顺序:左孩子 -> 右孩子 -> 根节点
  3. 我们可以发现:后序遍历是先序遍历的逆序序列,利用这一性质,我们进行后续遍历操作
  4. 这里我们需要两个辅助栈
  5. 首先,我们按照先序遍历的方式遍历整颗二叉树,并将遍历结果存入栈1中;
  6. 然后,再将栈1中的结果全部出栈,并存入数组中即可。

C代码

  1. 递归

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    /**
    * Definition for a binary tree node.
    * struct TreeNode {
    * int val;
    * struct TreeNode *left;
    * struct TreeNode *right;
    * };
    */

    /**
    * Note: The returned array must be malloced, assume caller calls free().
    */
    void visit(struct TreeNode *root, int *arr, int *returnSize)
    {
    if (root)
    {
    visit(root->left, arr, returnSize);
    arr[(*returnSize)++] = root->val;
    visit(root->right, arr, returnSize);
    }
    }

    int *inorderTraversal(struct TreeNode *root, int *returnSize)
    {
    *returnSize = 0;
    if (!root)
    return NULL;
    int *arr = (int *)malloc(1000 * sizeof(int));
    visit(root, arr, returnSize);
    return arr;
    }
  2. 迭代

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    #define maxSize 1000
    int *postorderTraversal(struct TreeNode *root, int *returnSize)
    {
    *returnSize = 0;
    if (!root)
    return NULL;
    int *arr = (int *)malloc(maxSize * sizeof(int));
    struct TreeNode *Stack1[maxSize];
    int top1 = -1;
    struct TreeNode *Stack2[maxSize];
    int top2 = -1;
    struct TreeNode *p = NULL;
    Stack1[++top1] = root;
    while (top1 != -1)
    {
    p = Stack1[top1--];
    Stack2[++top2] = p;
    if (p->left != NULL)
    Stack1[++top1] = p->left;
    if (p->right != NULL)
    Stack1[++top1] = p->right;
    }
    //the stack2 push is the postOrderNonRecursion
    while (top2 != -1)
    {
    p = Stack2[top2--];
    arr[(*returnSize)++] = p->val;
    }
    return arr;
    }

    Python代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
    def helper(root):
    if not root:
    return
    helper(root.left)
    helper(root.right)
    res.append(root.val)

    res = []
    helper(root)
    return res