前序遍历 递归版
编程思想
即借助系统栈，效率较低。二叉树的前序遍历规则:1. 访问根结点； 2. 遍历左子树； 3. 遍历右子树
编程实现
//树的定义
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
private:
void rec(TreeNode* root,vector<int> &ret){
if(root != nullptr){
ret.push_back(root->val);
rec(root->left,ret);
rec(root->right,ret);
}
}
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ret;
rec(root,ret);
return ret;
}
};
编程总结
常规方法，注意向量要用引用。
前序遍历 迭代版
编程思想
使用了一个辅助结点p，这种写法其实可以看作是一个模版，对应的还有中序和后序的模版写法，形式很统一，方便于记忆。
辅助结点p初始化为根结点，while循环的条件是栈不为空或者辅助结点p不为空，在循环中首先判断如果辅助结点p存在，那么先将p加入栈中，然后将p的结点值加入结果res中，此时p指向其左子结点。否则如果p不存在的话，表明没有左子结点，我们取出栈顶结点，将p指向栈顶结点的右子结点。
编程实现
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> s;
TreeNode *p = root;
while (!s.empty() || p) {
if (p) {
s.push(p);
res.push_back(p->val);
p = p->left;
}
else {
TreeNode *t = s.top();
s.pop();
p = t->right;
}
}
return res;
}
};
题目总结
在掌握规律的前提下，使用模板记忆。
中序遍历 递归版
编程思想
即借助系统栈，效率较低。二叉树的前序遍历规则:1. 遍历左子树； 2. 访问根结点； 3. 遍历右子树
编程实现
class Solution {
private:
void rec(TreeNode* root,vector<int> &ret){
if(root != NULL){
rec(root->left,ret);
ret.push_back(root->val);
rec(root->right,ret);
}
}
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ret;
rec(root,ret);
return ret;
}
};
题目总结
常规。
中序遍历 迭代版
编程思想
使用了一个辅助结点p，这种写法其实可以看作是一个模版，对应的还有前序和后序的模版写法，形式很统一，方便于记忆。
因为中序遍历的顺序是左-根-右，故与前序不同的是把结点值加入结果res的步骤从if中移动到了else中。
辅助结点p初始化为根结点，while循环的条件是栈不为空或者辅助结点p不为空，在循环中首先判断如果辅助结点p存在；那么先将p加入栈中，将p指向栈顶结点的左子结点。否则如果p不存在的话，表明没有左子结点，我们取出栈顶结点，然后将p的结点值加入结果res中，此时p指向其右子结点。
编程实现
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> s;
TreeNode *p = root;
while (!s.empty() || p) {
if (p) {
s.push(p);
p = p->left;
}
else {
TreeNode *t = s.top();
s.pop();
res.push_back(t->val);
p = t->right;
}
}
return res;
}
};
题目总结
注意与前序遍历的区别和联系，因为中序遍历的顺序是左-根-右，故与前序不同的是把结点值加入结果res的步骤从if中移动到了else中。
后序遍历 递归版
编程思想
即借助系统栈，效率较低。二叉树的前序遍历规则: 1. 遍历左子树；2. 遍历右子树；3. 访问根结点；
编程实现
class Solution {
private:
void rec(TreeNode* root,vector<int> &ret){
if(root != NULL){
rec(root->left,ret);
rec(root->right,ret);
ret.push_back(root->val);
}
}
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ret;
rec(root,ret);
return ret;
}
};
编程总结
常规。
后序遍历 迭代版
编程思想
使用了一个辅助结点p，这种写法其实可以看作是一个模版，对应的还有前序和中序的模版写法，形式很统一，方便于记忆。
由于后序遍历的顺序是左-右-根，而前序遍历的顺序是根-左-右，二者其实还是很相近的，我们可以先在先序遍历的方法上做些小改动，使其遍历顺序变为根-右-左，然后翻转一下，就是左-右-根了。翻转的方法，是反向加入结果res，每次都在结果res的开头加入结点值，而改变先序遍历的顺序就只要改变一下入栈顺序，先左后右，这样出栈处理的时候就是先右后左了。一定要对比前序遍历记忆！！！
拓展：当访问一个结点*p时，栈中结点恰好为*p结点的所有祖先。从栈底到栈底结点再加上*p结点，刚好构成从根节点到*p结点的一条路径。这一特性非常重要，如求根结点到某结点的路径；求两个结点的最近公共祖先；均可用这个思想。
编程实现
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> s;
TreeNode *p = root;
while (!s.empty() || p) {
if (p) {
s.push(p);
res.insert(res.begin(), p->val); //反向添加，而前序是正向添加
p = p->right; //与前序对比
}
else {
TreeNode *t = s.top();
s.pop();
p = t->left;
}
}
return res;
}
};
编程总结
拓展思想很重要！！
层次遍历 版本1
编程思想
进行常规层次遍历，需要借助一个队列。
先将根节点入队，然后出队，访问该根结点，如果它有左子树，则将左子树根节点入队，形成下一层；如果它有右子树，则将右子树根结点入队，形成下一层。然后出队，访问该结点，如此反复，直至队列为空。看代码比较容易懂。
补充：
queue 的基本操作有：
入队，如例：q.push(x); 将x 接到队列的末端。
出队，如例：q.pop(); 弹出队列的第一个元素，注意，并不会返回被弹出元素的值。
访问队首元素，如例：q.front()，即最早被压入队列的元素。
访问队尾元素，如例：q.back()，即最后被压入队列的元素。
判断队列空，如例：q.empty()，当队列空时，返回true。
访问队列中的元素个数，如例：q.size()
编程实现
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>>v;
queue<TreeNode*>q;
q.push(root); //根节点入队
if(root == NULL)
return v ;
while(!q.empty()){ //队列不空
vector<int>vv;
queue<TreeNode*> next ; // 建立第二个队列 用来存放下一层的结点
while(!q.empty()){ //遍历当前层的结点 这层循环是核心 其他都是为了满足OJ输出
TreeNode* tre = q.front() ;
vv.push_back(tre->val); //访问该结点,为了满足输出要求，所以有点复杂，
q.pop(); //对头元素出队
if(tre->left!=NULL){ //它有左子树
next.push(tre->left);
}
if(tre->right!=NULL){ //它有右子树
next.push(tre->right);
}
}
v.push_back(vv);
q=next; // // 遍历完后进入下一层
}
return v;
}
};
编程总结
层次遍历往往要用到队列，要对队列的基本操作熟悉，注意二维向量的生成。
层次遍历 版本2
编程思想
给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）。
同版本一类似，只不过需要多一个栈，把每层返回的结点加入栈中，最后输出。
编程实现
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>>v;
stack<vector<int>>s;
queue<TreeNode*>q;
q.push(root); //根节点入队
if(root == NULL)
return v ;
while(!q.empty()){ //队列不空
vector<int>vv;
queue<TreeNode*> next ; // 建立第二个队列 用来存放下一层的结点
while(!q.empty()){ //遍历每层的结点 这层循环是核心 其他都是为了满足OJ输出
TreeNode* tre = q.front() ;
vv.push_back(tre->val); //访问该结点,为了满足输出要求，所以有点复杂，
q.pop(); //对头元素出队
if(tre->left!=NULL){ //它有左子树
next.push(tre->left);
}
if(tre->right!=NULL){ //它有右子树
next.push(tre->right);
}
}
s.push(vv); //将每层结点入栈
//v.push_back(vv);
q=next; // // 遍历完后进入下一层
}
while(!s.empty()){ //将每层结点倒序输出
v.push_back(s.top());
s.pop();
}
return v;
}
};
编程总结
注意其他数据结构的配合使用。