145.二叉树的后序遍历

发表于 | 分类于
字数统计: 476 | 阅读时长 ≈ 2

题目描述

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

示例:

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