LeetCode刷题知识点总结——二叉树
一、二叉树理论基础
1.满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。通俗话理解：从底层开始到顶部的所有节点都全部填满的二叉树。深度为k，则有2^k-1个节点
2.完全二叉树：除了最底层节点没有节满，其余每层节点都达到最大值，并且最底层节点全都从最左边开始，按照顺序节若干个节点，中间不能出现空缺部分。
3.搜索二叉树：是一个有序树，遵循左节点小于根节点、右节点大于根节点的原则依次从上到下排列展开。
4.平衡搜索二叉树：是指满足左子树与右子树的高度差不超过1要求的搜索二叉树。
二、二叉树的定义与遍历
1.遍历方法：前序（根左右）、中序（左根右）、后序（左右根）；
2.二叉树可用链表和数组定义，链表定义符合深度搜索法，数组定义按照层级搜索（根节点位置为i，则其左右节点位置分别为2i+1,2i+2）。
struct treeNode{
int val;//数值
treeNode* left;//左指针
treeNode* right;//右指针
treeNode(int x): val(x),left(NULL),right(NULL) {} // 构造函数
三、二叉树递归遍历
递归三步曲：
1.递归函数的参数和返回值
void traversal(TreeNode* cur, vector<int>& vec) //vec用于存放节点数值
2.确定终止条件：当遍历节点为空时，就return
if (cur == NULL) return;
3.单层递归逻辑
//前序遍历
vec.push_back(cur->val); // 中
traversal(cur->left, vec); // 左
traversal(cur->right, vec); // 右
前序遍历完整代码
class Solution {
public:
void traversal(TreeNode* cur, vector<int>& vec) {
if (cur == NULL) return;
vec.push_back(cur->val); // 中
traversal(cur->left, vec); // 左
traversal(cur->right, vec); // 右
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
traversal(root, result);
return result;
}
};//后序和中序遍历只需要把交换三个节点位置即可完成
四、二叉树迭代法遍历（栈结构）
//前序遍历:中左右
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> result;
if (root == NULL) return result;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top(); // 中
st.pop();
result.push_back(node->val);
if (node->right) st.push(node->right); // 右 栈先进后出
if (node->left) st.push(node->left); // 左
}
return result;
}
};
?
//后序遍历：左右中 === 中左右->中右左->左右中
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> result;
if (root == NULL) return result;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top(); //中
st.pop();
result.push_back(node->val);
if (node->left) st.push(node->left); // 左
if (node->right) st.push(node->right); // 右
}
reverse(result.begin(), result.end()); // 将结果反转之后就是左右中的顺序了
return result;
}
};
?
//中序遍历
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
TreeNode* cur = root;
while (cur != NULL || !st.empty()) {
if (cur != NULL) {
st.push(cur);
cur = cur->left;