144.二叉树的前序遍历

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

题目描述

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

示例:

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

输出: [1,2,3]

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

题解

算法描述

  • 递归
  • 迭代

思路

这里主要说一下迭代法：

  1. 先序遍历的顺序：根节点 -> 左孩子 -> 右孩子
  2. 首先需要声明一个辅助栈，
  3. 先访问根节点，并将其val存到数组中
  4. 接下来该访问左孩子，由于栈是FILO，所以遍历时要先让右孩子入栈，才能让左孩子先出栈
  5. 循环这个过程，直至遍历全部节点

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)
        {
            arr[(*returnSize)++] = root->val;
            visit(root->left, arr, returnSize);
            visit(root->right, arr, returnSize);
        }
    }

    int *preorderTraversal(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 *preorderTraversal(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;
        stack[++top] = p;
        while (top != -1)
        {
            p = stack[top--];
            arr[(*returnSize)++] = p->val;
            //stack is FILO,so the preOrder push the rchild into the stack first
            if (p->right != NULL)
                stack[++top] = p->right;
            if (p->left != NULL)
                stack[++top] = p->left;
        }
        return arr;
    }

    Python代码

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

            res = []
            helper(root)
            return res