目录
1.搜索二叉树
1.1概念
1.2操作
1.2.1.查找
1.2.2插入
1.2.3遍历
1.2.4删除（重点）
1.3K模型/KV模型
1.4性能分析
2.二叉树oj
1.创建字符串
2.层序遍历
3.二叉树的最近公共祖先
4.二叉搜索树与双向链表
5.前序中序构建二叉树
6.中序后续构造二叉树
7.二叉树前序遍历(迭代)
8.二叉树中序遍历(迭代）
9.二叉树后序遍历(迭代)
1.搜索二叉树
1.1概念
搜索二叉树又称二叉排序树，可以是空树，也可满足下列性质：
1.若左子树不为空，则左子树上所有节点的值都比根节点的值小
2.若右子树不为空，则右子树上所有节点的值都比根节点的值大
3.左右子树也都是搜索二叉树
1.2操作
1.2.1.查找
根据二叉搜索树的特性，只要不停地跟当前节点的值比较大小，查找值大，就往当前节点右子树继续走，小，就往当前节点左子树继续走。
直到遇到空（即该树不存在查找的值）或遇到查找的值。
具体代码为了不水文，就不单独摘出来了，待会放在最下面
1.2.2插入
根据二叉搜索树的特性，前期也是不停的比较，但这时候，是直到找到一个空节点即可。
申请新的节点再赋给该空节点指针，另外，在查找的过程，除了当前节点cur，还有个父节点parent，实时更新，在最后，将赋值了新的空间的原空节点指针作为parent的孩子节点。
具体代码同理看下面
1.2.3遍历
比较方便的中序，而二叉搜索树的中序遍历正好就是一个递增的遍历。
所以直接用中序即可。
1.2.4删除（重点）
删除要分析很多种情况。
1.删除的节点没有孩子。
2.删除的节点有1个孩子。
3.删除的节点有2个孩子。
第一种和第二种可以在实现的时候可以归类为一种。
针对第一种和第二种，我们采取的是托付。都是将当前要删除节点的一个孩子托付给父节点，第一种情况下，托付哪个孩子都一样，都是空。第二种情况，托付那唯一的孩子即可。
而第三种情况。
我们采取替换法。托付法也可以，但是情况会很复杂，要针对复杂的二叉搜索树做预设。
替换进来的对象是哪个呢？有2种，选一个即可
比如上图，我们要删除3，那么第一种就是在3的左子树中找最右边的节点（一直找当前节点的右子树，直到找到右子树为空的节点，比如上图的2.3），第二种，就是3的右子树中找最左边的节点（一直找当前节点的左子树，直到找到左子树为空的节点。如上图的4）。
简单点概括，就是左树的最大节点，右树的最小节点
替换的时候要注意，如果找到的节点不是叶子节点，需要把另一个孩子托付给父节点（因为找到的节点必有一个空节点，但有没有孩子不一定）。
具体代码看下面。
#pragma once//搜索二叉树节点 template<class K> struct BSTreeNode {typedef BSTreeNode<K> Node;BSTreeNode(const K&key) :_key(key),_left(nullptr),_right(nullptr){}Node* _left;//左孩子指针Node* _right;//右孩子指针K _key;//存的值 }; //搜索二叉树 template<class K> class BSTree {typedef BSTreeNode<K> Node; public://强制生成默认构造，因为我们手动写了拷贝构造就不会自动生成默认构造了BSTree() = default;//拷贝构造函数BSTree(const BSTree<K>& t){_root = Copy(t._root);}//赋值BSTree<K>& operator=(BSTree<K> t){//利用传值拷贝，会生成一个新的节点值相同但地址不同的新搜索二叉树的特性//外面的二叉树会传值拷贝给t，t等于一个空间地址不同，但节点内,存的值跟外面的二叉树一模一样的新二叉树//这时候将两者_root交换，这样本二叉树就等于有了跟原先t一模一样的值和节点地址。//再利用局部变量在函数结束会自动销毁的特性，完全不需要理会形参t，其会自动销毁。swap(_root, t._root);return *this;}//插入-循坏bool Insert(const K& key){if (!_root)//第一个值插入，直接放{_root = new Node(key);return true;}//cur是用来搜索的指针,parent是cur的父节点指针Node* parent = nullptr;Node* cur = _root;while (cur)//cur不为空，就继续，直到找到了值或cur为空{if (cur->_key > key)//cur当前的存的值比我们插入的值大{parent = cur;//层层递进cur = cur->_left;}else if (cur->_key < key)//同理，右子树{parent = cur;//同理cur = cur->_right;}else//说明找到了，但我们这里是插入，而二叉搜索树根据定义，是各个值都是严格大于小于，所以是不能存在重复的//所以，这里遇到了已经存在情况，那就返回false，不执行插入{return false;}}//执行到这里，是说明cur已经是空指针了。cur = new Node(key);if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}return true;//}//插入-递归bool InsertR(const K& key){return _InsertR(_root, key);}//查找-循坏bool Find(const K& key){//cur是用来搜索的指针Node* cur = _root;while (cur)//cur不为空，就继续，直到找到了值或cur为空{if (cur->_key > key)//cur当前的存的值比我们找的大，说明目标最多可能在cur的左子树{cur = cur->_left;}else if (cur->_key < key)//同理，右子树{cur = cur->_right;}else//说明找到了。{return true;}}return false;//如果是以为空条件退出循坏，那说明二叉树中没有我们指定的数，所以默认false}//查找-递归bool FindR(const K& key){return _FindR(_root, key);}//中序-递归void InOrder()//注意，因为_root是private成员。不能在外面调用，所以写个子函数，在类里面调用即可{_InOrder(_root);cout << endl;}//删除-循坏bool Erase(const K&key) {if (_root == nullptr)return false;//检查树是否为空Node* partent = nullptr;//父节点Node* cur = _root;//当前节点while (cur){//跟前面一样if (cur->_key > key){partent = cur;cur = cur->_left;}else if (cur->_key < key){partent = cur;cur = cur->_right;}else{//这里找到之后，就要开始判断了。//根据分析，第一种和第二种情况是一起的，因为叶子节点的孩子是两个空节点，不影响托付//左孩子为空或右孩子为空的情况，不管另一个孩子是不是空节点，都把另一个孩子托付给父节点if (cur->_left == nullptr){//注意，可能出现cur正好就是整个树的根节点，这时候partent是空的if (cur == _root){_root = cur->_right;}else{//托付的时候，要确定当前节点是父节点的左孩子还是右孩子，因为父节点可能是有2个孩子if (partent->_left == cur){partent->_left = cur->_right;}else{partent->_right = cur->_right;}}delete cur;return true;}else if (cur->_right==nullptr){if (cur == _root){_root = cur->_left;}else{if (partent->_left == cur){partent->_left = cur->_left;}else{partent->_right = cur->_left;}}delete cur;return true;}else{//左右孩子都不为空情况//替换法，本次写右树最小//右树最小的父节点，注意，要直接把cur赋给他//因为如果右树最小有可能正好就是cur的右孩子，如果给空的话，后面执行托付的//时候可能出现访问空指针的情况。Node* rightMinPartent = cur;Node* rightMin = cur->_right;while (rightMin->_left){rightMinPartent = rightMin;rightMin = rightMin->_left;}cur->_key = rightMin->_key;//替换值//注意，右树最小节点可能是其父节点的左孩子也可能右孩子，托付的时候要判断先。if (rightMinPartent->_right == rightMin){rightMinPartent->_right = rightMin->_right;}else{rightMinPartent->_left = rightMin->_right;}delete rightMin;return true;}}}return false;}//删除-递归bool EraseR(const K& key){return _EraseR(_root, key);}//析构函数~BSTree() {Destroy(_root);}private://复制Node* Copy(Node* root){if (root == nullptr)return nullptr;Node* newNode = new Node(root->_key);newNode->_left = Copy(root->_left);newNode->_right = Copy(root->_right);return newNode;}//销毁-递归void Destroy(Node* root) {if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}//插入-递归-子bool _InsertR(Node*&root,const K& key)//注意，这里加了引用，是因为当我们递归到空指针的时候，除非加参数，否则找不到父节点//但是，加了引用，这个空指针是父节点的孩子指针的别名，这样直接赋值给root，就可以实现插入新节点{if (root == nullptr){root = new Node(key);return true;}if (root->_key < key){_InsertR(root->_right, key);}else if (root->_key > key){_InsertR(root->_left, key);}else return false;}//删除-递归-子bool _EraseR(Node*& root, const K& key){//这里的引用跟上面插入的是同理的if (root == nullptr)return false;if (root->_key < key){_EraseR(root->_right, key);}else if (root->_key > key){_EraseR(root->_left, key);}else{Node* del = root;//依靠&，甚至不需要考虑root是父节点的哪个孩子//因为递归传递的是父节点的某个孩子指针，接受的是对应的别名。if (root->_left == nullptr){root = root->_right;}else if (root->_right == nullptr){root = root->_left;}else{//这里不能依靠&，因为&是针对递归不停的传参，从而达到目的//但是循环的时候，&的对象是不能改变的，只能改变引用对象的值。Node* rightMin = root->_right;while (rightMin->_left){rightMin = rightMin->_left;}//这里取巧一手，交换两者的值，继续递归，因为删是根据值来删，//这样递归下去，最后删除会采用上面的逻辑，因为右子树最小节点的左孩子必是空指针。swap(root->_key, rightMin->_key);return _EraseR(root->_right, key);}delete del;return true;}}//查找-递归-子bool _FindR(Node* root, const K& key){if (root == nullptr)return false;if (root->_key < key){_FindR(root->_right, key);}else if (root->_key > key){_FindR(root->_left, key);}else return true;}//中序-递归-子void _InOrder(Node* root) {if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}//根节点Node* _root = nullptr; };1.3K模型/KV模型
上面的代码是K模型。
K模型：查找key是否存在搜索二叉树中，例如：小区车库，门禁
KV模型：根据key在搜索二叉树中查找value，例如：商城车库（跟小区车库有很大区别，因为小区车库除非保安手动开杠，否则基本只有小区的人才能进，逻辑很简单，是小区的人就开，不是就不开。但是商城不同，商城有些是收费的，这个时候车牌号是key，进入时间是value）、字典查询、高铁站进站刷身份证。
KV模型：
//搜索二叉树节点template<class K,class V>struct BSTreeNode {typedef BSTreeNode<K,V> Node;BSTreeNode(const K& key,const V&value):_key(key), _left(nullptr), _right(nullptr),_value(value){}Node* _left;//左孩子指针Node* _right;//右孩子指针K _key;//存的值V _value;};//搜索二叉树template<class K,class V>class BSTree {public:typedef BSTreeNode<K, V> Node;//插入-循坏bool Insert(const K& key,const V&value){//value不会影响节点在搜索二叉树里面的位置，只需要记得new的时候加上即可if (!_root)//第一个值插入，直接放{_root = new Node(key,value);return true;}//cur是用来搜索的指针,parent是cur的父节点指针Node* parent = nullptr;Node* cur = _root;while (cur)//cur不为空，就继续，直到找到了值或cur为空{if (cur->_key > key)//cur当前的存的值比我们插入的值大{parent = cur;//层层递进cur = cur->_left;}else if (cur->_key < key)//同理，右子树{parent = cur;//同理cur = cur->_right;}else//说明找到了，但我们这里是插入，而二叉搜索树根据定义，是各个值都是严格大于小于，所以是不能存在重复的//所以，这里遇到了已经存在情况，那就返回false，不执行插入{return false;}}//执行到这里，是说明cur已经是空指针了。cur = new Node(key,value);if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}return true;//}//查找-循坏Node* Find(const K& key){//find在这里需要做到，给key，返回相应节点//cur是用来搜索的指针Node* cur = _root;while (cur)//cur不为空，就继续，直到找到了值或cur为空{if (cur->_key > key)//cur当前的存的值比我们找的大，说明目标最多可能在cur的左子树{cur = cur->_left;}else if (cur->_key < key)//同理，右子树{cur = cur->_right;}else//说明找到了。{return cur;}}return nullptr;//如果是以为空条件退出循坏，那说明二叉树中没有我们指定的数，所以默认false}//中序-递归void InOrder()//注意，因为_root是private成员。不能在外面调用，所以写个子函数，在类里面调用即可{_InOrder(_root);cout << endl;}//删除-循坏bool Erase(const K& key) {//没有变化，value不影响节点在搜索二叉树里的位置if (_root == nullptr)return false;//检查树是否为空Node* partent = nullptr;//父节点Node* cur = _root;//当前节点while (cur){//跟前面一样if (cur->_key > key){partent = cur;cur = cur->_left;}else if (cur->_key < key){partent = cur;cur = cur->_right;}else{//这里找到之后，就要开始判断了。//根据分析，第一种和第二种情况是一起的，因为叶子节点的孩子是两个空节点，不影响托付//左孩子为空或右孩子为空的情况，不管另一个孩子是不是空节点，都把另一个孩子托付给父节点if (cur->_left == nullptr){//注意，可能出现cur正好就是整个树的根节点，这时候partent是空的if (cur == _root){_root = cur->_right;}else{//托付的时候，要确定当前节点是父节点的左孩子还是右孩子，因为父节点可能是有2个孩子if (partent->_left == cur){partent->_left = cur->_right;}else{partent->_right = cur->_right;}}delete cur;return true;}else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (partent->_left == cur){partent->_left = cur->_left;}else{partent->_right = cur->_left;}}delete cur;return true;}else{//左右孩子都不为空情况//替换法，本次写右树最小//右树最小的父节点，注意，要直接把cur赋给他//因为如果右树最小有可能正好就是cur的右孩子，如果给空的话，后面执行托付的//时候可能出现访问空指针的情况。Node* rightMinPartent = cur;Node* rightMin = cur->_right;while (rightMin->_left){rightMinPartent = rightMin;rightMin = rightMin->_left;}cur->_key = rightMin->_key;//替换值//注意，右树最小节点可能是其父节点的左孩子也可能右孩子，托付的时候要判断先。if (rightMinPartent->_right == rightMin){rightMinPartent->_right = rightMin->_right;}else{rightMinPartent->_left = rightMin->_right;}delete rightMin;return true;}}}return false;}private://中序-递归void _InOrder(Node* root) {if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}//根节点Node* _root = nullptr;};
1.4性能分析
对于搜索二叉树来说，不管是插入还是删除，效率主要取决于查找的速度。
而对于查找，最优的情况可以接近于log2 N，如左图，但最坏情况下，O(N)如右图。
2.二叉树oj
1.创建字符串
606. 根据二叉树创建字符串 - 力扣（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:// bool dfs(TreeNode*root)// {// if(root==nullptr)return false;// res+=(to_string(root->val));// res+='(';// if(dfs(root->left))res+=')';// else res.pop_back();// if(root->left==nullptr&&root->right!=nullptr)res+="()";// res+='(';// if(dfs(root->right))res+=')';// else res.pop_back();// return true;// }string tree2str(TreeNode* root) {// dfs(root);// return res;if(root==nullptr)return "";res+=to_string(root->val);if(root->left||root->right){res+='(';tree2str(root->left);res+=')';}if(root->right){res+='(';tree2str(root->right);res+=')';}return res;}string res="";//被我注释的代码，在速度上是更快点的，因为每次下面的代码每次都要返回string类型，需要消耗时间创建string返回对象，而我注释的代码返回一个bool类型，是比较节省的，下面的代码是条理比较清晰的 };2.层序遍历
102. 二叉树的层序遍历 - 力扣（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:struct kp{kp(TreeNode*r=NULL,int l=-1){rt=r;level=l;}TreeNode* rt;int level; }; //存对象，rt是节点指点，level是第几层vector<vector<int>> levelOrder(TreeNode* root) {queue<kp>mp;mp.emplace(root,0); //root默认0层vector<vector<int>>res(0);if(root==nullptr)return res;vector<int>lp(0);while(!mp.empty()){auto tmp=mp.front();TreeNode*a=tmp.rt;int h=tmp.level;mp.pop();if(a!=nullptr){mp.emplace(a->left,h+1);mp.emplace(a->right,h+1);if(h>res.size()){res.push_back(lp);lp.resize(0);}lp.push_back(a->val);}}res.push_back(lp);return res;}};107. 二叉树的层序遍历 II - 力扣（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:struct kp{kp(TreeNode*r=NULL,int l=-1){rt=r;level=l;}TreeNode* rt;int level; };vector<vector<int>> levelOrder(TreeNode* root) {queue<kp>mp;mp.emplace(root,0);vector<vector<int>>res(0);if(root==nullptr)return res;vector<int>lp(0);while(!mp.empty()){auto tmp=mp.front();TreeNode*a=tmp.rt;int h=tmp.level;mp.pop();if(a!=nullptr){mp.emplace(a->left,h+1);mp.emplace(a->right,h+1);if(h>res.size()){res.push_back(lp);lp.resize(0);}lp.push_back(a->val);}}res.push_back(lp);return res;}vector<vector<int>> levelOrderBottom(TreeNode* root) {vector<vector<int>>res=levelOrder(root);reverse(res.begin(),res.end());return res;} };3.二叉树的最近公共祖先
236. 二叉树的最近公共祖先 - 力扣（LeetCode）
O(N^2)，核心是如果两个节点分别在左子树和右子树，自己即为最近公共祖先。
基本是压线过的，稍微为难点就嘎了
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/ class Solution { public:bool intree(TreeNode*root,TreeNode*x){if(root==NULL)return false;return root==x||intree(root->left,x)||intree(root->right,x);}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root==NULL)return NULL;bool pl,pr,ql,qr;if(root==p||root==q)return root;pl=intree(root->left,p);pr=!pl;ql=intree(root->left,q);qr=!ql;if((pl&&qr)||(pr&&ql)){return root;}else if(pl&&ql){return lowestCommonAncestor(root->left,p,q);}else{return lowestCommonAncestor(root->right,p,q);}} };O(N),利用栈，记录路径。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/ class Solution { public:bool dfs(TreeNode*root,TreeNode*x,int i){if(root==NULL)return false;if(i==1)p1.push(root);if(i==2)q1.push(root);if(root==x)return true;if(dfs(root->left,x,i))return true;if(dfs(root->right,x,i))return true;if(i==1)p1.pop();if(i==2)q1.pop();return false;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {dfs(root,p,1);dfs(root,q,2);while(p1.size()>q1.size())p1.pop();while(p1.size()<q1.size())q1.pop();while(p1.top()!=q1.top())p1.pop(),q1.pop();return p1.top();}stack<TreeNode*> p1,q1; };4.二叉搜索树与双向链表
二叉搜索树与双向链表_牛客题霸_牛客网 (nowcoder.com)
中序遍历，prev是前驱的节点，root是当前节点，本质上是将二叉树线索化
/* struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {} };*/ class Solution { public:void InOrder(TreeNode*root,TreeNode*&prev){if(root==nullptr)return;InOrder(root->left,prev);if(prev==nullptr)res=root;root->left=prev;if(prev)prev->right=root;prev=root;InOrder(root->right,prev);}TreeNode* Convert(TreeNode* pRootOfTree) {TreeNode*p=nullptr;InOrder(pRootOfTree,p);return res;}TreeNode*res; };5.前序中序构建二叉树
105. 从前序与中序遍历序列构造二叉树 - 力扣（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:unordered_map<int,int>mp;TreeNode* dfs(vector<int>& preorder, vector<int>& inorder,int l,int r,int &i){if(l>r)return NULL;TreeNode* root=new TreeNode(preorder[i++]);int x=mp[root->val];root->left=dfs(preorder,inorder,l,x-1,i);root->right=dfs(preorder,inorder,x+1,r,i);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int index=0;for(int i=0;i<inorder.size();i++)mp[inorder[i]]=i;return dfs(preorder,inorder,0,preorder.size()-1,index);} }; 照着前序走，前序确定根，中序确定子树区间6.中序后续构造二叉树
106. 从中序与后序遍历序列构造二叉树 - 力扣（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:unordered_map<int,int>mp;TreeNode*dfs(vector<int>& inorder,vector<int>& postorder,int l,int r,int &in){if(l>r)return NULL;TreeNode*root=new TreeNode(postorder[in--]);int x=mp[root->val];root->right=dfs(inorder,postorder,x+1,r,in);root->left=dfs(inorder,postorder,l,x-1,in);return root;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {int i=postorder.size()-1;for(int i=0;i<inorder.size();i++)mp[inorder[i]]=i;return dfs(inorder,postorder,0,inorder.size()-1,i);} }; 注意，我们递归只能按根的顺序下去，所以，后序遍历的话，我们要从根，右子树，左子树的顺序构建二叉树 而前面前序遍历的题，之所以看着递归顺序很像前序遍历，其实最重要的前序遍历是根左子树右子树，所以不用额外内容。这里后序遍历就要考虑如何从根开始构建二叉树。7.二叉树前序遍历(迭代)
144. 二叉树的前序遍历 - 力扣（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) {TreeNode* cur = root;stack<TreeNode*>s;vector<int>res(0);while (!s.empty()||cur)//当栈不为空说明还有某个节点的右子树没遍历\ //cur是为了针对，此时cur正是最后一个右子树的根节点，但是栈已经pop掉了，为空了的情况{while (cur)//以cur为根节点，一直往左走，把东西放进去res，s{res.push_back(cur->val);s.push(cur);cur = cur->left;}cur = s.top()->right;//此时，开始提出栈顶节点，访问这个节点的右子树s.pop();}return res;} };
先访问左路，再访问右树,因为是前序遍历，所以访问左路的时候就要放入数组
8.二叉树中序遍历(迭代）
94. 二叉树的中序遍历 - 力扣（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) {TreeNode* cur = root;stack<TreeNode*>s;vector<int>res(0);while (!s.empty()||cur){while (cur){s.push(cur);cur = cur->left;}TreeNode*top=s.top();res.push_back(top->val);cur = top->right;s.pop();}return res;} };9.二叉树后序遍历(迭代)
145. 二叉树的后序遍历 - 力扣（LeetCode）
根本的思路跟前面的前序中序差不多。
后序遍历的时候，我们会发现一个问题，那就是根节点，是可能会被访问两次的。
第一次，是左子树访问完，然后到了根节点，再去右子树。
第二次，是右子树访问完，又回到了根节点。
一种方案是每个节点都配一个标记变量，一种就是如下的。
首先我们注意，一个根节点第一次被取到的时候，说明该根节点的左子树已经被访问完了，这时候我们前一个访问的节点（也可以认为是当前栈顶元素的前一个栈顶元素），正是左子树的根节点（或空，反正左子树肯定是被访问完了）。第二次被访问到的时候，前一个访问的节点有多种可能（一个是当前根节点的兄弟，当前根节点的左子树根节点（说明右子树是空），当前根节点的右子树根节点，总归而言右子树肯定是被访问了的）。
据此，我们可以这样判断，每次if判断，当前根节点的右子树是否是空，以及是否是前一个访问的节点。当前根节点的右子树是空，按照遍历的思路，也可以认为这就是后序遍历中的当前根节点的前一个访问节点（只是是空罢了）；如果当前根节点的右子树直接或间接（空）是前一个访问节点，那么说明，右子树已经被访问过了，结合前面的，左子树肯定被访问过了，那么这时候，就是把根节点放入遍历数组，同时记得取走栈顶元素，更新 前一个访问的节点。
/*** 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) {TreeNode* cur = root;stack<TreeNode*>s;vector<int>res(0);while (!s.empty()||cur){while (cur){s.push(cur);cur = cur->left;}TreeNode*top=s.top();res.push_back(top->val);cur = top->right;s.pop();}return res;}vector<int> postorderTraversal(TreeNode* root) {TreeNode* cur = root;stack<TreeNode*>s;TreeNode*prev=nullptr;vector<int>res(0);while (!s.empty()||cur){while (cur){s.push(cur);cur = cur->left;}TreeNode*top=s.top();if(top->right==nullptr||top->right==prev){s.pop();res.push_back(top->val);prev=top;}else{cur = top->right;}}return res;} };
