94.二叉树的中序遍历

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

题目描述

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

示例:

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

输出: [1,3,2]

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

题解

算法描述

  • 递归
  • 迭代

思路

这里主要说一下迭代法：

  1. 中序遍历的顺序：左孩子 -> 根节点 -> 右孩子
  2. 首先需要声明一个辅助栈，
  3. 先访问左孩子，由于这是一个类似递归的过程，所以要一直沿着左孩子的方向一直向左下遍历，并将节点压入栈中；
  4. 找到整颗二叉树中最左下的孩子后，将其val存到数组中
  5. 接下来该访问根节点，继续出栈，即可得到根节点
  6. 然后在访问根节点的右孩子
  7. 循环这个过程，直至遍历全部节点

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
    /**
     * 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
    #define maxSize 1000
    int* inorderTraversal(struct TreeNode* root, int* returnSize)
    {
        *returnSize = 0;
        if (!root)
            return NULL;
        int* arr = (int*)malloc(maxSize * sizeof(int));
        struct TreeNode *stack[maxSize], *p = root;
        int top = -1;
        //the Stack may be empty in the process,
        //so the condition that p != NULL can keep the loop continue
        while (top != -1 || p != NULL) {
            while (p != NULL) {
                stack[++top] = p;
                p = p->left;
            }
            p = stack[top--];
            arr[(*returnSize)++] = p->val;
            p = p->right;
        }
        return arr;
    }

    Python代码

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

            res = []
            helper(root)
            return res

    不知道为什么辅助函数写到函数外边就不可以，是力扣官方的编译器问题吗？奇奇怪怪🙃