题目链接
https://leetcode-cn.com/problems/binary-tree-preorder-traversal/description/
题解一:递归
// Problem: LeetCode 144
// URL: https://leetcode-cn.com/problems/binary-tree-preorder-traversal/description/
// Tags: Tree Recursion Stack
// Difficulty: Medium
#include <iostream>
#include <vector>
using namespace std;
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x):val(x), left(nullptr), right(nullptr){}
};
class Solution{
public:
void traversal(TreeNode* root, vector<int>& result){
if (root != nullptr){
result.push_back(root->val);
if(root->left!=nullptr)
traversal(root->left, result);
if(root->right!=nullptr)
traversal(root->right, result);
}
}
vector<int> preorderTraversal(TreeNode* root){
vector<int> result;
traversal(root, result);
return result;
}
};
int main()
{
cout << "helloworld" << endl;
// system("pause");
return 0;
}
题解二:非递归
- 需要用到栈
- 注意循环条件
- 注意是先把右子树存入栈中
// Problem: LeetCode 144
// URL: https://leetcode-cn.com/problems/binary-tree-preorder-traversal/description/
// Tags: Tree Recursion Stack
// Difficulty: Medium
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x):val(x), left(nullptr), right(nullptr){}
};
class Solution{
public:
vector<int> preorderTraversal(TreeNode* root){
vector<int> result;
stack<TreeNode*> nodes;
if(root!=nullptr)
nodes.push(root);
while(!nodes.empty()){
root = nodes.top();
nodes.pop();
if(root!=nullptr){
result.push_back(root->val);
nodes.push(root->right);
nodes.push(root->left);
}
}
return result;
}
};
int main()
{
cout << "helloworld" << endl;
// system("pause");
return 0;
}
题解三:非递归(通过栈模拟递归)
思路:https://www.cnblogs.com/chouxianyu/p/13293284.html
// Problem: LeetCode 144
// URL: https://leetcode-cn.com/problems/binary-tree-preorder-traversal/description/
// Tags: Tree Recursion Stack
// Difficulty: Medium
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x):val(x), left(nullptr), right(nullptr){}
};
class Solution{
public:
vector<int> preorderTraversal(TreeNode* root){
vector<int> result;
stack<TreeNode*> nodes;
if(root!=nullptr)
nodes.push(root);
while(!nodes.empty()){
// 取出节点
root = nodes.top();
nodes.pop();
// 将节点对应的树拆解成前序,模拟递归解法中的函数调用
if(root!=nullptr){
if(root->right!=nullptr)
nodes.push(root->right);
if(root->left!=nullptr)
nodes.push(root->left);
nodes.push(root);
nodes.push(nullptr); // 设置nullptr标志
}
// nullptr代表栈顶对应的树(根、左子树、右子树)已按照指定顺序遍历,一层递归函数运行结束
else{
result.push_back(nodes.top()->val);
nodes.pop();
}
}
return result;
}
};
int main()
{
cout << "helloworld" << endl;
// system("pause");
return 0;
}
作者:@臭咸鱼
转载请注明出处:https://www.cnblogs.com/chouxianyu/
欢迎讨论和交流!