XTAO's Tech Blog
0%

[Leetcode]144. Binary Tree Preorder Traversal(C++)

发表于 更新于 分类于 ， 评论数：
1.4k 1 分钟

题目描述

题目链接：144. Binary Tree Preorder Traversal

Given the root of a binary tree, return the preorder traversal of its nodes‘ values.

例子

例子 1

Input: root = [1,null,2,3]
Output: [1,2,3]

例子 2

Input: root = []
Output: []

例子 3

Input: root = [1]
Output: [1]

例子 4

Input: root = [1,2]
Output: [1,2]

例子 5

Input: root = [1,null,2]
Output: [1,2]

Constraints

The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100

Follow Up

Recursive solution is trivial, could you do it iteratively?

解题思路

递归的方法比较容易，这里放一个迭代版本，用栈可以实现类似的效果。如果我们始终往往栈中先放入右子树再放入左子树，每次取栈顶节点的值放入结果中。这样就会优先处理左子树，因此可以以
preorder 的顺序输出值，代码如下：

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;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
#include <vector>
#include <stack>

class Solution {
public:
    std::vector<int> preorderTraversal(TreeNode* root) {
        std::vector<int> result;
        if (!root) return result;
        std::stack<TreeNode*> s;
        s.push(root);
        while (!s.empty()) {
            TreeNode* curr = s.top();
            s.pop();
            result.push_back(curr->val);
            if (curr->right) s.push(curr->right);
            if (curr->left) s.push(curr->left);
        }
        return result;
    }
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(h)

GitHub 代码同步地址： 144.BinaryTreePreorderTraversal.cpp

其他题目：
GitHub: Leetcode-C++-Solution
博客： Leetcode-Solutions

推荐文章