目录
力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
- /**
- * 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) {}
- * };
- */
- class Solution {
- public:
- vector<int> preorderTraversal(TreeNode* root) {
- vector<int> v;
- stack
s; - TreeNode*cur = root;
-
- while(cur!=nullptr || !s.empty())
- //cur为空表示结点为空,栈为不为空表示还有右子树没访问
- {
- //访问一棵树的开始
- //1. 访问左路结点,左路结点入栈
- while(cur!=nullptr)
- {
- v.push_back(cur->val);
- s.push(cur);
- cur = cur->left;
- }
- //依次访问左路结点的右子树
- TreeNode*tmp = s.top();
- s.pop();
- cur = tmp->right;
- }
- return v;
- }
- };
力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
- /**
- * 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) {}
- * };
- */
- class Solution {
- public:
- vector<int> inorderTraversal(TreeNode* root) {
- stack
s;//栈中存放待访问的结点 - vector<int>v;
- TreeNode*cur = root;
- while(cur!=nullptr || !s.empty())
- {
- while(cur!=nullptr)//while循环是将左路结点进行了入栈
- {
- s.push(cur);
- cur = cur->left;
- }
- TreeNode*tmp = s.top();//从栈中开始取数据,代表左子树已经访问完了
- s.pop();
- v.push_back(tmp->val);//先访问根
- cur = tmp->right;//去到右子树
- }
- return v;
- }
- };
- /**
- * 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) {}
- * };
- */
- class Solution {
- public:
- vector<int> postorderTraversal(TreeNode* root) {
- stack
s; - vector<int> v;
- TreeNode* cur = root;
- TreeNode* prev = nullptr;//prev记录上一个访问的结点
- while(cur!=nullptr || !s.empty())
- {
- while(cur!=nullptr)
- {
- s.push(cur);
- cur = cur->left;
- }
-
- TreeNode* tmp = s.top();
- if(tmp->right == nullptr || tmp->right == prev)
- //如果tmp的右为空或者上一个访问的是tmp的右,此时就可以访问tmp
- {
- v.push_back(tmp->val);
- s.pop();
- prev = tmp;//更新tmp
- }
- else//tmp结点的右没有访问过,此时先访问tmp的右
- {
- cur = tmp->right;
- }
- }
- return v;
- }
- };