二叉树的4种遍历-递归+迭代

• 二叉树的前序遍历
  • 递归写法
  • 迭代写法
• 二叉树的中序遍历
  • 递归写法
  • 迭代写法
• 二叉树的后序遍历
  • 递归写法
  • 迭代写法
  • 转换写法
• 莫里斯Morris遍历
• 层次遍历
  • 迭代写法
  • 递归写法

二叉树的前序遍历

前序遍历：root left-child right-child

题源：Leetcode 144

递归写法

//Preorder
class Solution {
public:
    vector preorderTraversal(TreeNode* root) {//参数为二叉树的根结点
        //如果结点非空
        if(root){
            ret.push_back(root->val);//访问根结点
            preorderTraversal(root->left);//遍历左子树
            preorderTraversal(root->right);//遍历右子树
        }
        return ret;
    }
private:
    vector ret;//返回值  
};

迭代写法

首先，初步了解一下迭代是什么概念：

迭代是重复反馈过程的活动，其目的通常是为了逼近所需目标或结果。每一次对过程的重复称为一次“迭代”，而每一次迭代得到的结果会作为下一次迭代的初始值。

理解例子：

迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0，用某种数学方法导出等价的形式x=g(x），然后按以下步骤执行：

⑴ 选一个方程的近似根，赋给变量x0;

⑵ 将x0的值保存于变量x1，然后计算g(x1），并将结果存于变量x0;

⑶ 当x0与x1的差的绝对值还大于指定的精度要求时，重复步骤⑵的计算^[1]。

对题目的迭代分析：

递归本质上和栈上差不多，本题的迭代方式实际上就是在模拟递归的过程。使用stack来模拟系统栈

stack来存放结点指针，出栈表示访问数据，非空则入栈。先序序列中先左后右访问，所以入栈时先右后左

class Solution {
public:
	vector preorderTraversal(TreeNode* root) {
		stack s;//头文件
        //先判断根结点是否为空
		if (root == NULL)
			return ret;
		s.push(root);//root非空
        
		while (!s.empty()) {//迭代结束（成功）条件
			TreeNode* get = s.top();
			//出栈模拟访问该结点
			ret.push_back(get->val);
			s.pop();

			//再判断左右子树的压栈
			if (get->right)
				s.push(get->right);
			if (get->left)
				s.push(get->left);
		}
		return ret;
	}
private:
	vector ret;//返回值
};

前两种时间空间复杂度均为O(n)，不过使用递归比较容易有堆栈溢出的风险

二叉树的中序遍历

前序遍历：left-child root right-child

题源：Leetcode 94

递归写法

class Solution {
public:
    vector inorderTraversal(TreeNode* root) {
        if(root){
            inorderTraversal(root->left);
            ret.push_back(root->val);
            inorderTraversal(root->right);
        }
        return ret;
    }
private:
    vector ret;
};

迭代写法

基于栈的遍历算法

class Solution {
public:
	vector inorderTraversal(TreeNode* root) {
		stack s;
		TreeNode* p = root;		
		while (p || !s.empty()) {
            //利用第二个循环来进行入栈操作
			while (p) {
				s.push(p);
				p = p->left;//一直压入左子树
			}
			p = s.top();
			ret.push_back(p->val);//访问
			s.pop();
			p = p->right;//遍历右子树
		}
		return ret;
	}
private:
	vector ret;//返回
};

二叉树的后序遍历

前序遍历：left-child right-child root

题源：Leetcode 145

递归写法

class Solution {
public:
    vector postorderTraversal(TreeNode* root) {
        if(root){
            postorderTraversal(root->left);
            postorderTraversal(root->right);
            ret.push_back(root->val);
        }
        return ret;
    }
private:
    vector ret;
};

迭代写法

二叉树的后序遍历迭代算法会比较复杂，一个结点的出栈与否跟其是否有右子树有关。

class Solution {
public:
	vector postorderTraversal(TreeNode* root) {
		stack s;
		TreeNode* p = root;
		TreeNode* last = NULL;//记录前一个访问的结点
		while (p || !s.empty()) {
			while (p) {
				s.push(p);
				p = p->left;
			}
			
			p = s.top();
            //若右节点已经访问过或者没有右节点 则输出该节点值
			if (!p->right || p->right == last) {
				s.pop();
				ret.push_back(p->val);
				last = p;
				p = NULL;
			}
			else {
				p = p->right;
				last = NULL;//可有可无
			}
		}
		return ret;
	}
private:
	vector ret;
};

转换写法

前序遍历的非递归比后序遍历更容易理解一些

前序遍历：根 左 右

后序遍历：左 右 跟

改写前序遍历为：根 右 左 再进行逆序，即为后序遍历

class Solution {
public:
	vector preorderTraversal(TreeNode* root) {
		stack s;//头文件
        //先判断根结点是否为空
		if (root == NULL)
			return ret;
		s.push(root);//root非空
        
		while (!s.empty()) {//迭代结束（成功）条件
			TreeNode* get = s.top();
			//出栈模拟访问该结点
			ret.push_back(get->val);
			s.pop();

			//不同于先序，先压左
			if (get->left)
				s.push(get->right);
			if (get->right)
				s.push(get->left);
		}
        ret.reverse(ret.size());//vector的逆序需要额外开销
		return ret;
	}
private:
	vector ret;//返回值
};

vector的逆序开销比较大，可以选择其他的实现形式比如链表等。

莫里斯Morris遍历

其实是一种动态的二叉树线索化，省去了栈的空间，空间复杂度为O(1)，但实际应用并不广，先埋个坑在这里。

层次遍历

层次遍历就是逐层遍历树的结构，相当于广度优先搜索，通常使用队列来做广度优先搜索。

题源：Leetcode 102

本题的主要关键是还要梳理出层次来，相较于以前写过的层次遍历输出

//直接层次遍历输出，无梳理层次，非本题题解
void function(TreeNode* root){
	TreeNode* p=root;
    queue Q;
    if(p)
        Q.push(p);
    
    while(!Q.empty()){
        p=Q.front();
        cout<data<left)
            Q.push(Q->left);
        if(Q->right)
            Q.push(Q->right);
	}
}

而本题要求按照层次梳理，需要了解每一层的结点个数

迭代写法

广度遍历的思想，时间空间复杂度均为O(n)

class Solution {
public:
	vector> levelOrder(TreeNode* root) {
		vector> ret;//返回
		vector p;//临时一维vector
		queue Q;//队列
		TreeNode* T = root;
		
		if (T == NULL)
			return ret;

		Q.push(T);
		while (!Q.empty()) {
			int size = Q.size();//本层次的结点数目
			p.clear();//重置临时vector
            //固定数目的同层次结点pop
			for (int i = 0; i < size; i++) {
				T = Q.front();
				p.push_back(T->val);
				Q.pop();
				if (T->left)
					Q.push(T->left);
				if (T->right)
					Q.push(T->right);
			}
			ret.push_back(p);//一次循环结束，意味着一次层次遍历结束
		}		
		return ret;
	}
};

递归写法

先埋个坑