题目描述
题目链接：144. Binary Tree Preorder Traversal
Given the
rootof 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 的顺序输出值，代码如下：
/**
* 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