0%

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

题目描述

题目链接: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