[数据结构与算法] 二叉树的统一迭代法

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 二叉树的统一迭代法 -> 正文阅读

[数据结构与算法]二叉树的统一迭代法

二叉树的统一迭代法

笔记内容来源于《代码随想录（二叉树—二叉树的统一迭代法）》
迭代法实现的先中后序，风格不统一，除了先序和后序，有关联，中序完全是另外一个风格。我们寄希望于找到一种迭代法可以写出一种统一风格的代码。

主体思路是：我们将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记（要处理的是“中”），标记的方法是，要处理的节点放入栈之后，紧接着放入一个空指针作为标记。

迭代法中序遍历

class Solutiuon{
public:
	vector<int> inorderTraversal(TreeNode* root){
		vector<int> result;
		stack<TreeNode*> st;
		if(root == nullptr) return result;
		while(!result.empty()){
			TreeNode * p = st.top();
			if(p!=nullptr){
			     //中序遍历的方式为：左中右，入栈方式为 右中(标记)左
				st.pop(); //将该节点弹出，避免重复操作
				if(p->right!=nullptr) st.push(p->right);  //添加右节点
				st.push(p);                              // 添加中节点（要处理）
				st.push(nullptr);                        // 添加标记空指针
				if(p->left!nullptr) st.push(p->left);    // 添加左节点
			}
			else
			{
			    //处理过程
				st.pop();
				p = st.top();
				st.pop();
				result.push_back(p->val);
			}
		}
		return result;	
	}
};

迭代法前序遍历

class Solution{
public:
	vector<int> preorderTraversal(TreeNode* root){
		vector<int> result;
		stack<TreeNode*> st;
		if(root == nullptr) return result;
		st.push(root);
		while(!st.empty()){
			TreeNode * p = st.top();
			if(p!=nullptr){
				 st.pop();
				 if(p->right!=nullptr) st.push(p->right);
				 if(p->left!= nullptr) st.push(p->left);
				 st.push(p);
				 st.push(nullptr);
			}
			else
			{
				st.pop();
				p = st.top();
				st.pop();
				ans.push_back(p->val);
			}	
		}
		return result;	
	}
};

迭代法后序遍历

class Solution{
public:
	vector<int> preorderTraversal(TreeNode* root){
		vector<int> result;
		stack<TreeNode*> st;
		if(root ==nullptr) return result;
		st.push(root);
		while(!st.empty()){
			TreeNode* p = st.top();
			if(p!=nullptr){
				st.pop()
				st.push(p);
				st,push(nullptr);
				if(p->right!=nullptr) st.push(p->right);
				if(p->left!= nullptr) st.push(p->left);
			}
			else
			{
				st.pop();
				p = st.top();
				st.pop();
				result.push_back(p->val);
			}
		}
		return result;
	}
};