基础知识:
所有的题都是建立在二叉树的前序遍历,中序遍历,后序遍历(它们的递归版与非递归版),及层次遍历。搜索二叉树及平衡二叉树。搜索二叉树是指按照中序遍历,它是从小到大排序的(所以考搜索二叉树基本考中序遍历)。平衡二叉树是指根节点的左右子树总结点相差不能超过1。
参考代码:(上面的遍历方式标准版)
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
using namespace std;
struct tree_node{
int val;
tree_node* left;
tree_node* right;
tree_node(int x) :val(x), left(NULL), right(NULL){}
};
class Solution{
public:
//前序遍历,递归与非递归版,根 左 右
void front_d(tree_node* head)
{
if (head == NULL)
return;
cout << head->val << endl;
front_d(head->left);
front_d(head->right);
}
void front(tree_node* head)
{
if (head == NULL)
return;
stack<tree_node*> node_stack;
tree_node* pMove = head;
while (pMove || !node_stack.empty())
{
while (pMove)
{
cout << pMove->val << endl;
node_stack.push(pMove);
pMove = pMove->left;
}
if (!node_stack.empty())
{
pMove = node_stack.top();
node_stack.pop();
pMove = pMove->right;
}
}
}
//中序遍历,递归和非递归版,左 根 右
void middle_d(tree_node* head)
{
if (head == NULL)
return;
middle_d(head->left);
cout << head->val << endl;
middle_d(head->right);
}
void middle(tree_node* head)
{
if (head == NULL)
return;
stack<tree_node*> node_stack;
tree_node* pMove = head;
while (pMove || !node_stack.empty())
{
while (pMove)
{
node_stack.push(pMove);
pMove = pMove->left;
}
if (!node_stack.empty())
{
pMove = node_stack.top();
node_stack.pop();
cout << pMove->val << endl;
pMove = pMove->right;
}
}
}
//后序遍历,递归与非递归版,左 右 根
void back_d(tree_node* head)
{
if (head == NULL)
return;
back_d(head->left);
back_d(head->right);
cout << head->val << endl;
}
void back(tree_node* head)
{
if (head == NULL)
return;
stack<tree_node*> node_stack;
tree_node* pMove = head;
tree_node* flag = NULL;
while (pMove)
{
node_stack.push(pMove);
pMove = pMove->left;
}
while (!node_stack.empty())
{
pMove = node_stack.top();
node_stack.pop();
if (pMove->right == NULL || pMove->right == flag)
{
cout << pMove->val << endl;
flag = pMove;
}
else{
node_stack.push(pMove);
pMove = pMove->right;
while (pMove)
{
node_stack.push(pMove);
pMove = pMove->left;
}
}
}
}
//奇偶层次遍历
void cc_traverse(tree_node* head)
{
if (head == NULL)
return;
queue<tree_node*> odd_q;
queue<tree_node*> even_q;
tree_node* pMove = head;
odd_q.push(head);
while (!odd_q.empty() || !even_q.empty())
{
while (!odd_q.empty())
{
pMove = odd_q.front();
odd_q.pop();
cout << pMove->val << " ";
if (pMove->left)
even_q.push(pMove->left);
if (pMove->right)
even_q.push(pMove->right);
}
cout << endl;
while (!even_q.empty())
{
pMove = even_q.front();
even_q.pop();
cout << pMove->val << " ";
if (pMove->left)
odd_q.push(pMove->left);
if (pMove->right)
odd_q.push(pMove->right);
}
cout << endl;
}
}
};
int main()
{
Solution solution;
tree_node tree_node1(1);
tree_node tree_node2(2);
tree_node tree_node3(3);
tree_node tree_node4(4);
tree_node tree_node5(5);
tree_node tree_node6(6);
tree_node tree_node7(7);
tree_node1.left = &tree_node2;
tree_node1.right = &tree_node3;
tree_node2.left = &tree_node4;
tree_node2.right = &tree_node5;
tree_node3.left = &tree_node6;
tree_node3.right = &tree_node7;
tree_node4.left = NULL;
tree_node4.right = NULL;
tree_node5.left = NULL;
tree_node5.right = NULL;
tree_node6.left = NULL;
tree_node6.right = NULL;
tree_node7.left = NULL;
tree_node7.right = NULL;
solution.cc_traverse(&tree_node1);
system("pause");
return 0;
}
上面是必备基础知识,下面是力扣1-150题中的二叉树题目:
博客索引:
94.二叉树的中序遍历:
https://blog.csdn.net/L_smartworld/article/details/107365297
95.不同的二叉搜索树 II:
https://blog.csdn.net/L_smartworld/article/details/107365448
96.不同的二叉搜索树:
https://blog.csdn.net/L_smartworld/article/details/107365789
98.验证二叉搜索树:
https://blog.csdn.net/L_smartworld/article/details/107406797
100.相同的树:
https://blog.csdn.net/L_smartworld/article/details/107406978
101.对称二叉树:
https://blog.csdn.net/L_smartworld/article/details/107407096
102.二叉树的层序遍历:
https://blog.csdn.net/L_smartworld/article/details/107407314
103. 二叉树的锯齿形层次遍历:
https://blog.csdn.net/L_smartworld/article/details/107407697
104. 二叉树的最大深度:
https://blog.csdn.net/L_smartworld/article/details/107411335
105. 从前序与中序遍历序列构造二叉树:
https://blog.csdn.net/L_smartworld/article/details/107411449
106. 从中序与后序遍历序列构造二叉树:
https://blog.csdn.net/L_smartworld/article/details/107411641
107. 二叉树的层次遍历 II:
https://blog.csdn.net/L_smartworld/article/details/107427667
108. 将有序数组转换为二叉搜索树:
https://blog.csdn.net/L_smartworld/article/details/107427704
109. 有序链表转换二叉搜索树:
https://blog.csdn.net/L_smartworld/article/details/107427762
110. 平衡二叉树:
https://blog.csdn.net/L_smartworld/article/details/107427795
111.二叉树的最小深度:
https://blog.csdn.net/L_smartworld/article/details/107463981
112.路径总和:
https://blog.csdn.net/L_smartworld/article/details/107464166
113.路径总和 II:
https://blog.csdn.net/L_smartworld/article/details/107464369
114.二叉树展开为链表:
https://blog.csdn.net/L_smartworld/article/details/107464575
116.填充每个节点的下一个右侧节点指针:
https://blog.csdn.net/L_smartworld/article/details/107492388
117.填充每个节点的下一个右侧节点指针 II:
https://blog.csdn.net/L_smartworld/article/details/107492618
124.二叉树中的最大路径和:
https://blog.csdn.net/L_smartworld/article/details/107541464
129.求根到叶子节点数字之和:
https://blog.csdn.net/L_smartworld/article/details/107700110
144.二叉树的前序遍历:
https://blog.csdn.net/L_smartworld/article/details/107761716
145.二叉树的后序遍历:
https://blog.csdn.net/L_smartworld/article/details/107761779
235.二叉搜索树的最近公共祖先:
https://blog.csdn.net/L_smartworld/article/details/107245923
236.二叉树的最近公共祖先:
https://blog.csdn.net/L_smartworld/article/details/107246390
剑指offer:(最新版,与上面重复就不罗列了)
8.二叉树的下一个节点:
https://blog.csdn.net/L_smartworld/article/details/105490529
26.树的子结构:
https://blog.csdn.net/L_smartworld/article/details/104655031
27.二叉树的镜像:
https://blog.csdn.net/L_smartworld/article/details/104655595
33.二叉搜索树的后序遍历序列:
https://blog.csdn.net/L_smartworld/article/details/104793879
37.序列化二叉树:
https://blog.csdn.net/L_smartworld/article/details/105583848
54.二叉搜索树的第K大节点:
https://blog.csdn.net/L_smartworld/article/details/105611668