二叉树的非递归遍历（前序）
思路
代码
void preorderNoRecursion(btNode* p)
{
if (p != NULL)
{
int top = -1;
btNode* stack[50];
btNode* temp;
stack[++top] = p;
while (top != -1)
{
temp = stack[top--];
std::cout << temp->data << ' '; //viist
if (temp->rc != NULL)
stack[++top] = temp->rc;//push right child
if (temp->lc != NULL)
stack[++top] = temp->lc;//push left child
}
}
}
二叉树的非递归遍历（中序）
思路
代码
void Inorder_I(BiTree T)//中序的非递归遍历
{
stacks;
BiTree p=T;
while(p!=NULL||!s.empty())//栈不空或P不空时循环
{
if(p) //一路向左
{
s.push(p); //当前节点入栈
p=p->lchild; //左孩子不空，一直往左走
}
else //出栈，并转向出栈节点的右子树
{
p=s.top();
cout<data;
s.pop(); //栈顶元素出栈，访问出栈节点
p=p->rchild; //返回while循环继续进入if-else语句
}
}
}
二叉树的非递归遍历（后序）
思路
先序遍历顺序的根-左-右改为根-右-左
用这个栈把结果存起来，然后输出，就是后序遍历
代码
void postorderNoRecursion(btNode* p)
{
if (p != NULL)
{
btNode* stack1[50];//栈1为辅助栈
btNode* stack2[50];//栈2为访问栈
int top1 = -1, top2 = -1;
btNode* temp;
stack1[++top1] = p;
while (top1 != -1)//修改先序非递归遍历进行交换
{
temp = stack1[top1--];
stack2[++top2] = temp;
if (temp->lc != NULL)
stack1[++top1] = temp->lc;//先入左孩子结点
if (temp->rc != NULL)
stack1[++top1] = temp->rc;//后入右孩子结点
}
while (top2 != -1)//再逆序
std::cout << stack2[top2--]->data << ' ';//访问栈2中的数据
}
}
二叉树的层序遍历
思路
代码
class Solution { //二叉树的层次遍历
public:
vector> levelOrder(TreeNode* root) {
vector> result;
queue que;
if (root != nullptr){
que.push(root);
}
while (!que.empty()) {
vector temp;
int length = que.size();
for (int i = 0; i < length; ++i) {
TreeNode* tempNode = que.front();
que.pop();
temp.push_back(tempNode->val);
if (tempNode->left) {
que.push(tempNode->left);
}
if (tempNode->right) {
que.push(tempNode->right);
}
}
result.push_back(temp);
}
return result;
}
};
求二叉树的最大宽度
思路
层序遍历的变体，用一个map做记录，把每一个node 的层数作为key，value就是遍历一个+1
遍历完树就可以拿到所有层的宽度
也可以不使用map，多使用一个队列，一层使用一个队列，当一个队列为NULL时，另外一个队列达到最大值，记录一下这个层的number，一样可以做到上面的效果。
代码
int function(Node* head) {
if (head == NULL)
return 0;
unordered_map m;//装每个结点以及对应的第几层
queue q;//宽度优先遍历
q.push(head);//先将头装进去
int max_w = 0;//记录最大宽度
int h = 0;//第几层
int floor[100] = { 0 };//每一层的结点个数
m.insert(make_pair(head, h));
while (!q.empty()) {
//取出元素
Node* cur = q.front();//头拿出来
q.pop();//弹出去
//给压入的元素标号
h = m[cur];
if (cur->left != NULL) {
q.push(cur->left);
m.insert(make_pair(cur->left, h + 1));
}
if (cur->right != NULL) {
q.push(cur->right);
m.insert(make_pair(cur->right, h + 1));
}
floor[h]++;
}
//寻找每一层的最大结点数
for (int i = 0;i <= h-1;i++)
max_w = max_w < floor[i] ? floor[i] : max_w;
return max_w;
}
二叉树的序列化与反序列化（前序方式）
思路
序列化和反序列化出了中序存在歧义，其他的方式都可以转（后序可以转为变体前序）。
反序列化的过程和序列化的过程也非常相似，核心就是占位符#。
非递归的前序反序列化主要是：
代码
//序列化函数 void serialization(btree* head, queue* que) { //前序遍历入队--(递归法) if (!head) { //节点为空则返回 NULL 并 return que->push(NULL); return; } que->push(head->data); //入队 serialization(head->left, que); //左子树入队 serialization(head->right, que); //右子树入队 } //反序列化函数 - 递归版本 btree* bulidTree(queue * que) { //按前序遍历入队的顺序依次出队, 建树 int num = que->front(); //获取队头元素 que->pop(); //出队 if (!num) { //若为空则返回 NULL return NULL; } btree* head = new btree; //非空则建立节点 head->data = num; //对节点赋值 head->left = bulidTree(que); //建立节点的左子树 head->right = bulidTree(que); //建立节点的右子树 return head; //返回节点 }
二叉树的序列化与反序列化（层序方式）
思路
层序方式的序列化和反序列化的核心在于标志空节点的占位符，比如#
序列化的时候需要NULL孩子，序列化为#
反序列化的时候，也是遍历的过程：
代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Codec {
public:
/*
解题思路：
1.序列比：将所有节点的val（包括空节点）按照层次遍历存储到string，空节点存入null，用逗号','隔开
2.反序列化：将string每个元素分解成stringArr存储每个元素，然后遍历
*/
// Encodes a tree to a single string.
string serialize(TreeNode* root)
{
if (root == nullptr)
return "#";
string result;
std::queue nodeQueue;
TreeNode* cur = nullptr;
int isValid = false;
int size = 0;
nodeQueue.push(root);
while (!nodeQueue.empty()) // 正常的层次遍历
{
size = nodeQueue.size();
for (int i = 0; i < size; ++i)
{
cur = nodeQueue.front();
nodeQueue.pop();
if (cur == nullptr) // 这里有区别，如果是空节点则存储为'#'
{
result.append("#,");
continue;
}
result.append(std::to_string(cur->val) + ","); // 存储节点信息
nodeQueue.push(cur->left); //这里有区别，不管是否空节点都压入栈
nodeQueue.push(cur->right); //这里有区别，不管是否空节点都压入栈
}
}
return result;
}
void toStrArr(const string& data, vector& valsStr)
{
string valStr;
valStr.reserve(10); // 优化，预分配10个byte
for (const char& ch : data)
{
if (ch == ',')
{
valsStr.push_back(valStr); // 将每个节点的值存入数组
valStr.clear(); // 初始化
}
else
{
valStr.push_back(ch); // 存储每个节点的值
}
}
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
if (data.compare("#") == 0) // 如果整个字符串为空，则直接返回nullptr
return nullptr;
vector valsStr; // 数组字符串存储每个节点信息
toStrArr(data, valsStr); // 将string转为数组字符串
int size = valsStr.size();
TreeNode* root = new TreeNode(std::stod(valsStr[0]));
TreeNode* parent = nullptr;
std::queue nodeQueue;
nodeQueue.push(root); // 将根节点压入栈
for (int i = 1; i < size; ++i)
{
parent = nodeQueue.front();
nodeQueue.pop();
if (valsStr[i].compare("#"))
{
parent->left = new TreeNode(std::stod(valsStr[i])); // 创建该节点左子节点
nodeQueue.push(parent->left); // 非空则压入栈，顺序访问每个节点
}
if (valsStr[++i].compare("#"))
{
parent->right = new TreeNode(std::stod(valsStr[i])); // 创建该节点右子节点
nodeQueue.push(parent->right); // 非空则压入栈，顺序访问每个节点
}
}
return root; // 返回原始二叉树
}
};
// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));
二叉树找到两个节点的最近公共祖先
题目
给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。
数据范围：树上节点数满足1≤n≤10^5, 节点值val满足区间 [0,n)
要求：时间复杂度O(n)
注：本题保证二叉树中每个节点的val值均不相同。
思路
这个题目是一个典型的树型动态规划，二叉树绝大多数的难题都是动态规划，比如说判断最大的线索二叉树（LeetCode——654），比如找到树上最远距离，本质上都是动态规划
按照动态规划的思路，就是把一个很大规模的问题，变成一个一个的小规模相同类型的问题，然后把结果进行逻辑处理，步步上传。
这个题目中找最近的公共祖先按照动态规划的思维去拆分就是：
代码