一、介绍

遍历二叉树（Traversing Binary Tree）是指按指定的规律对二叉树中的每个结点访问且仅访问一次。由于二叉树是一种非线性结构，需要寻找一种规律，使二叉树上的结点能排列在一个线性序列上，从而实现遍历。

树是一种特殊的图，即无环连通图。

由于二叉树的基本组成单位为根节点、左子树和右子树，以N、L、R分别代表其对应的单位。按从左至右的顺序，将其分为三种遍历：
（1）NLR先序遍历；（2）LNR中序遍历；（3）LRN后序遍历

同时，根据二叉树的层次，又可从上至下，从右至左进行遍历，这种遍历方式成为层次遍历。

其中，根据先序、后序和层次遍历可确定二叉树的根节点是哪个。同时，再结合中序遍历，可再找出二叉树的左右子树。因此，当想要构造二叉树时，必须要知道中序遍历的情况才能知道左右子树，必须要知道先序或后序或层次遍历情况，才能确定根节点。

具体实现上，先、后和中序遍历可用系统栈或用户栈来实现，层次遍历可用队列来实现。

非递归方式（用户栈）：
先和后序：通常采用遍历一个，弹出一个元素；
中序：通常采用一路遍历到底，再弹出。

二、先序遍历

（1）递归算法模板

先序遍历的递归方式，常采用一个全局变量或深拷贝的变量进行配合加减，在末尾会返回这个变量并退出。

void preorderTraversal(TreeNode *root){
	if(root == NULL)	return ;

	visit(root->data);
	preorderTraversal(root->left);
	preorderTraversal(root->right);
}

（2）非递归算法模板

1）遍历一个弹出一个
此方式是一层一层的向下遍历，遍历完一个结点，将结点所指向的左右孩子压入栈中，将此结点从栈中弹出。

优点：结构清晰，遍历对某一处进行
缺点：因为会将之前的元素弹出，因此若需要对之前的元素进行某些处理不适于用此方式。

void preorderTraversal(TreeNode* root) {
	if(root == NULL)			return ;
	stack<TreeNode*> st;
	st.push(root);
	while(!st.empty()) {         
		TreeNode* node = st.top();
		st.pop();
		visite(node->val);
		if(node->right != NULL)		st.push(node->right);		// 因为栈是先进后出，因此先压右，再压左，可保证弹出为先左后右
		if(node->left != NULL)		st.push(node->left);
	}
}

2）一路遍历到底，再弹出
此方式是一层一层的向下遍历，遍历到底时，才将栈中元素弹出。先遍历左子树并压栈，对元素进行访问，一下压倒底之后，弹出元素，然后再去遍历右子树。

优点： 因为之前的元素没有在遍历完时被弹出，因此回退时，可对之前的元素进行某些处理。
缺点： 结构不是非常清晰，通过每次为空指针时弹出一次元素，不便于对某一左、右或叶子写处理逻辑。

void preorderTraversal(TreeNode* root) {
	stack<TreeNode*> st;
	TreeNode* p = root;
	while(p || !st.empty()) {         
		while(p) {
			st.push(p);
			p = p->left';
		}
		TreeNode* node = st.top();
		st.pop();
		p = p->right;
	}
}

（3）实战例题

二叉树的先序遍历——递归+非递归

三、中序遍历

（1）递归算法模板

void inorderTraversal(TreeNode *root){
	if(root == NULL)		return ;

	inorderTraversal(root->left);
	visit(root->data);
	inorderTraversal(root->right);
}

（2）非递归算法模板

1）一路遍历到底，再弹出
此方式是一层一层的向下遍历，遍历到底时，才将栈中元素弹出。先遍历左子树并压栈，一下压倒底之后，弹出元素，进行访问，然后再去遍历右子树。
优点： 因此，若还需要对之前的元素进行某些处理可用此方式。
缺点： 结构不是非常清晰，通过每次为空指针时弹出一次元素，不便于对某一左、右或叶子写处理逻辑。

void inorderTraversal(TreeNode* root){
	stacck<TreeNode*> st;
	TreeNode* p = root;	
	while(p != nullptr || !st.empty()){
		while(p != nullptr){
			st.push(p);
			p = p->left;
		}
		p = st.top();
		st.pop();
		visit(node->data);
		p = p->right;
	}
}

（3）实战例题

二叉树的中序遍历——递归+非递归

四、后序遍历

（1）递归算法模板

后序遍历的递归方式，通常需要对底层的结点处理后，将信息返回给上一层结点，上一层的结点需要用到下面的信息进行返回。结点间的信息处理，通过利用栈返回的数值进行处理。

注：先序遍历，结点间的信息处理，通过一个深拷贝变量或全局变量进行处理。

void postorderTraversal(TreeNode* root){
    if(root == NULL)        return ;

    postorderTraversal(root->left);
    postorderTraversal(root->right);
    visit(root->data);
}

（2）非递归算法模板

1）遍历一个弹出一个
此方式是一层一层的向下遍历，遍历完一个结点，将结点所指向的左右孩子压入栈中，将此结点从栈中弹出。先存根结点，弹出一个结点访问一个结点，然后再压入左节点和右节点，以此方式遍历。最后得到中右左顺序的结点。再进行依次reverse(),得到左右中。

优点：结构清晰，遍历对某一处进行
缺点：因为会将之前的元素弹出，因此若需要对之前的元素进行某些处理不适于用此方式。

void postorderTraversal(TreeNode* root){
	if(root == nullptr)     return {};
	stack<TreeNode*> st;
	st.push(root);
	// 遍历一个，存一个，先按照中右左的顺序存储
	while(!st.empty()) {
		TreeNode* node = st.top();
		st.pop();
		visit(node->data);
		if(node->left != nullptr)       st.push(node->left);
		if(node->right != nullptr)      st.push(node->right);
	}
	// 反转，将中右左变成左右中
	reverse(res.begin(), res.end());
	return res;
}

（3）实战例题

二叉树的后序遍历——递归+非递归

五、层次遍历

使用一个队列实现，按层遍历并存入这一层的节点，下次遍历时，先获取该层的结点个数n，遍历这n个节点并将这n个节点的下一层孩子节点存入队列中。

算法模板

void levelorder(TreeNode* root){
/**
 * 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:
    void levelOrder(TreeNode* root) {
        if(root == nullptr)         return {};
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()) {
            // 获取一层的结点个数，遍历该层所有结点
            int n = que.size();
            while(n--) {
                TreeNode* node = que.front();
                que.pop();
                visit(node->val);
                // 将下一层的左右孩子存入队列中
                if(node->left != nullptr)      que.push(node->left);
                if(node->right != nullptr)     que.push(node->right);                
            }
        }
        return ;
    }
};
}

参考文章：二叉树层序遍历登场

实战例题

（1）自顶向下，按层次遍历获取结点

二叉树的层次遍历

（2）自底向上，按层次遍历获取结点

107.二叉树的层次遍历 II

（3）N-叉树，按层次遍历，将每层将孩子结点入队

√ 429. N 叉树的层序遍历
注意孩子结点的数据类型，按对应类型进行遍历

（4）层次遍历，计算每层的平均值

637.二叉树的层平均值

（5）层次遍历，计算每层的最大值

515. 在每个树行中找最大值

（6）按层次遍历，从左至右，最后一个元素为最右端元素

199. 二叉树的右视图

（7）按层次遍历，该层还有剩余元素，next指向后续元素，无剩余元素，next指向NULL

√ 116. 填充每个节点的下一个右侧节点指针
117. 填充每个节点的下一个右侧节点指针 II

（8）按层次遍历，每遍历一层高度加一，获取最大高度

√ 90、【栈与队列】leetcode ——104. 二叉树的最大深度：层次遍历+DFS+子问题分解（C++版本）

（9）按层次遍历，每遍历一层高度加一，获取最大深度

√ 91、【栈与队列】leetcode ——559.n叉树的最大深度（递归DFS+迭代BFS）（C++版本）

（10）按层次遍历，最小找到叶节点的为最短路径

√ 92、【栈与队列】leetcode ——111. 二叉树的最小深度：层次遍历+先序DFS+后序DFS[子问题分解]（C++版本）
（本题适于用BFS，不适于用DFS和子问题分解）