144.二叉树的前序遍历

题目描述

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

示例:

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