# 0144. 二叉树的前序遍历

### 题目地址(144. 二叉树的前序遍历)

<https://leetcode-cn.com/problems/binary-tree-preorder-traversal/>

### 题目描述

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

 示例:

输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,2,3]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？

```

### 前置知识

* 递归
* 栈

### 公司

* 阿里
* 腾讯
* 百度
* 字节

### 思路

这道题目是前序遍历，这个和之前的`leetcode 94 号问题 - 中序遍历`完全不一回事。

前序遍历是`根左右`的顺序，注意是`根`开始，那么就很简单。直接先将根节点入栈，然后 看有没有右节点，有则入栈，再看有没有左节点，有则入栈。 然后出栈一个元素，重复即可。

> 其他树的非递归遍历可没这么简单

![](https://p.ipic.vip/68yby8.jpg)

（迭代 VS 递归）

### 关键点解析

* 二叉树的基本操作（遍历）

  > 不同的遍历算法差异还是蛮大的
* 如果非递归的话利用栈来简化操作
* 如果数据规模不大的话，建议使用递归
* 递归的问题需要注意两点，一个是终止条件，一个如何缩小规模

1. 终止条件，自然是当前这个元素是 null（链表也是一样）
2. 由于二叉树本身就是一个递归结构， 每次处理一个子树其实就是缩小了规模， 难点在于如何合并结果，这里的合并结果其实就是`mid.concat(left).concat(right)`, mid 是一个具体的节点，left 和 right`递归求出即可`

### 代码

* 语言支持：JS，C++

JavaScript Code:

```js
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function (root) {
  // 1. Recursive solution

  // if (!root) return [];

  // return [root.val].concat(preorderTraversal(root.left)).concat(preorderTraversal(root.right));

  // 2. iterative solutuon

  if (!root) return [];
  const ret = [];
  const stack = [root];
  let t = stack.pop();

  while (t) {
    if (t.right) {
      stack.push(t.right);
    }
    if (t.left) {
      stack.push(t.left);
    }
    ret.push(t.val);
    t = stack.pop();
  }

  return ret;
};
```

C++ Code:

```
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> v;
        vector<TreeNode*> s;
        while (root != NULL || !s.empty()) {
            while (root != NULL) {
                v.push_back(root->val);
                s.push_back(root);
                root = root->left;
            }
            root = s.back()->right;
            s.pop_back();
        }
        return v;
    }
};
```

**复杂度分析**

* 时间复杂度：$O(N)$
* 空间复杂度：$O(N)$

### 相关专题

* [二叉树的遍历](/leetcode-solution/thinkings/binary-tree-traversal.md)

大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 ![](https://p.ipic.vip/j5i9l1.jpg)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/144.binary-tree-preorder-traversal.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.