目录
前序遍历
递归解法
这个没啥好说的，前序就是在调用递归函数访问左子树和右子树之前访问当前结点，注意点就是如果前序遍历序列要用数组存储的话，数组一定要定义在递归函数前边。还有递归出口是判断root是不是nullptr。
/** 递归的解法，注意要记录结点值得话要把数组放函数外边
* 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> v;
vector<int> preorderTraversal(TreeNode* root) {
// vector<int> v; 要用一个vector记录结点值，vector当然要放在函数的外边
if(root == nullptr) return v;
v.push_back(root->val);
preorderTraversal(root->left);
preorderTraversal(root->right);
return v;
}
};迭代解法
前序遍历的迭代解法要用栈来辅助，用循环迭代实现。
在while循环外边初始化栈，先将树的根结点入栈
在while循环内部，先将栈顶元素出栈存放到要输出的结果数组中去
然后判断该栈顶元素是否是nullptr
如果是nullptr的话，就直接continue，从栈中取下一个栈顶元素出来，因为这不是树中的结点，而是叶子结点的下一级，即空结点
如果不是nullptr，说明该结点的左右子树可能还有结点，当然也可能该节点是叶节点，但是可以确定的是该节点不是空的，因此把该结点的值存入结果数组ans，然后依次把该节点的右子树和左子树入栈。之所以先入栈左子树再入栈右子树，是因为栈后进先出，这样出栈访问结点的时候就是先左子树后右子树，这样才符合先序遍历的顺序。
/**
* 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> ans;
stack<TreeNode *> s;
s.push(root); //入栈二叉树树顶结点
while(!s.empty()){
TreeNode *node = s.top();
s.pop();
if(node == nullptr) continue;
ans.push_back(node->val);
s.push(node->right);
s.push(node->left);
}
return ans;
}
};分析：因为栈有后进先出的机制，因此可以保证每次循环的时候都只处理当前结点的先序遍历，最终可以模拟整棵树的先序遍历。而将当前代码的中的栈简单地改为队列，然后让左子树先入队，右子树后入队的方法是不行的。因为当左右子树结点入队以后，肯定先处理左子树结点是对的，但是处理左子树结点的时候，左子树的下一级左右子树结点会排在第一级右子树的后边，即这时候会先处理第一级右子树结点。也就是说，对于根节点来说，其左子树还没有遍历完，右子树就开始遍历了，这显然不符合树的先序遍历定义。而用栈的时候，处理左子树的下一级左右子树的时候，下一级左右子树的结点入栈之后是排在第一级右子树前边的，因此根节点的左子树还没处理完就处理右子树结点的情况。
中序遍历
递归解法
没啥好说的，访问当前结点放在递归调用左右子树之间就可以了。
/**
* 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> v;
vector<int> inorderTraversal(TreeNode* root) {
if(!root) return v;
inorderTraversal(root->left);
v.push_back(root->val);
inorderTraversal(root->right);
return v;
}
};迭代解法
与前序遍历的不同之处在于，前序遍历遍历到的第一个结点就是前序序列的第一个结点，而中序遍历遍历到的第一个结点是最左边的结点，但是这个结点不一定是叶子结点，如下图所示，中序序列的第一个结点并不一定是叶子结点，可以有右子树。
虽然也是用栈辅助，但是与前序遍历不同的是前序遍历的主要思想是遇到一个结点就先入栈，然后访问出战，再依次将其右左子树入栈，下一次循环的时候就是左子树先出栈了，然后在遍历左子树的孩子，直到左子树的孩子全部遍历完成，才是遍历右子树的孩子。而中序遍历因为第一个结点是最左边的结点，因此肯定要先用一个循环找到这个结点，即到左边最深处，然后访问这个结点，因为这个结点一定没有左子树，所以将这个结点访问以后就访问其右子树，首先将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:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode *> s;
while(root || !s.empty()){
while(root){ // 遍历到最深层的左子树左叶子,root=nullptr时候跳出循环
s.push(root);
root = root->left; // root的左子树为空右子树不一定为空
}
// 上边循环已经把第一个需要访问的左子树叶子找到了
// 先把此叶子访问，然后再处理该左叶子对应级别的右叶子
root = s.top(); // root从nullptr重新设置成栈顶元素，即最左叶子
s.pop();
ans.push_back(root->val);
root = root->right; //虽然最左叶子没有左子树，但是可以有右子树
}
return ans;
}
};后序遍历
递归解法
没啥好说的
/**递归的
* 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> v;
vector<int> postorderTraversal(TreeNode* root) {
if(root == nullptr) return v;
postorderTraversal(root->left);
postorderTraversal(root->right);
v.push_back(root->val);
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) {
vector<int> ans;
stack<TreeNode *> s;
s.push(root);
while(!s.empty()){
TreeNode *node = s.top();
s.pop();
if(node == nullptr) continue;
ans.push_back(node->val);
s.push(node->left); // 跟前序遍历的不同就是改成了从右到左
s.push(node->right);
}
reverse(ans.begin(), ans.end());
return ans;
}
};层次遍历
二叉树前中后序遍历的递归解法本质上都是用的DFS，DFS用递归的方式巧妙地隐式使用了栈。而层次遍历则需要使用BFS。层次遍历一般需要队列的辅助，即先定义一个辅助队列，并将根节点指针放入队列。然后在while循环中先访问队首元素即根节点，然后将根节点出队，接下来再依次将不为nullptr的左孩子和右孩子结点入队，这样循环遍历的方式刚好能形成一个层次遍历的序列。需要注意的是要在循环外边判断一下二叉树是否为空，否则循环引用里可能会出现指针越界的问题。
而这道题的关键是，要输出的不是层次遍历序列，而是一个二维数组，即要把每一层的结点分开，这就要求在while循环中加一个判断。即从第一次队列中只有一个根节点指针的时候，我们每次进入while循环都判断里边有多少个结点，然后用一个for处理这些结点，将这些结点的值都存入一个一维数组。这些结点就是二叉树同一层的结点。然后在for循环外边将一维数组汇总给二维数组，并将一维数组清空，以便于保存下一层的结点。需要注意的是这个一维数组要定义在for循环外边，否则将一维数组放入二维数组的时候会找不到，因为C++中一个{ }就是一个作用域。
当然如果不想用临时一维数组也行，即每次进入while循环都临时push_back一个一维数组，即
ans.push_back(vector<int>);然后可以用ans.back().push_back()来将每一层的结点放入数组。
/**
* 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<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode *> q;
q.push(root);
vector<vector<int>> ans;
vector<int> ans_temp;
if(root == nullptr) return ans;
while(!q.empty()){
int len = q.size(); //为了将每一层分开存储
for(int i = 0; i < len; ++i){
TreeNode *node = q.front();
q.pop();
ans_temp.push_back(node->val);
if(node->left != nullptr) q.push(node->left);
if(node->right != nullptr) q.push(node->right);
}
ans.push_back(ans_temp);
ans_temp.clear();
}
return ans;
}
};