二叉树理论基础
分类
-
满二叉树：只有度为0和度为2的结点，且度为0结点在同一层上（每一层的结点都是满的）。
-
完全二叉树：除了底层外其他层结点都是满的（底层当然也可以是满的），且底层结点从左往右连续不断。
-
二叉搜索树：
树的每个结点满足：
- 左子树所有结点值均小于根结点的值
- 右子树所有结点值均大于根结点的值
- 左右子树分别是二叉排序树
-
平衡二叉搜索树：二叉搜索树的基础上，满足左右子树高度差绝对值不超过1。
map、set、multimap、multiset底层实现就是平衡二叉树，所以增删操作时间复杂度为O(logN)，同时也是有序的。
存储方式
- 链式存储（链表）：结点元素、左指针、右指针。
- 线性/顺序存储（数组）：
2*i + 1是左孩子；2*i + 2是右孩子。
遍历方式
深度优先搜索DFS
- 前序遍历：中左右
- 中序遍历：左中右
- 后序遍历：左右中
广度优先搜索BFS
- 层序遍历
定义方式
// 链式为例
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x),left(NULL),right(NULL);
};
遍历二叉树
leetcode：
递归遍历
思路
前序遍历，中左右。
因此单层递归逻辑就是：1. 记录当前结点val；2. 递归当前结点左孩子；3. 递归当前结点右孩子。
复杂度分析
时间复杂度：O(N)。遍历一遍二叉树结点。
空间复杂度：O(N)。最坏情况下，二叉树完全偏斜成为一条链，递归深度会达到N。
注意点
递归三部曲
- 确定传入参数和返回值
- 确定终止条件
- 确定单层递归逻辑
代码实现
/**
* 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:
void preTraverse(TreeNode* root,vector<int>& result){
if(root == NULL)
return;
// 前序：中左右
result.push_back(root->val);
preTraverse(root->left,result);
preTraverse(root->right,result);
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
preTraverse(root,result);
return result;
}
};
迭代遍历（前序、后序）
思路
前序遍历为例，中左右。（后序遍历就是先入栈左孩子、再入栈右孩子，得到中右左，逆序得到左右中）
-
先把根节点放入栈中
-
元素出栈，val存入数组中；（注意判断非空结点）右孩子入栈、左孩子入栈。
（入栈为右、左，出栈才能是左、右）
复杂度分析
时间复杂度：O(N)。
空间复杂度：O(N)。
注意点
略
代码实现
/**
* 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> result;
stack<TreeNode*> st;
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;
}
};
迭代遍历（中序）
思路
- 遍历指针cur指向root
- 当指针和栈不同时为空时循环：当cur不为空时，入栈当前结点，指针指向左孩子；cur为空时，cur指向栈顶结点，栈顶元素pop，记录当前cur的val，cur指向右孩子。
复杂度分析
时间复杂度：O(N)。
空间复杂度：O(N)。
注意点
略
代码实现
/**
* 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:
// 迭代法中序
// 1.处理：result加入元素
// 2.访问：遍历结点
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result; // 结果数组
stack<TreeNode*> st; // 结点栈，记录遍历过的结点
TreeNode* cur = root; // 遍历指针
while(cur != NULL || !st.empty()){ // 当前指针不为空或栈不空
if(cur != NULL){ // cur不为空时，入栈当前结点
st.push(cur);
cur = cur->left;
}else{ // 否则出栈元素，记录当前结点，看右孩子
cur = st.top();st.pop();
result.push_back(cur->val);
cur = cur->right;
}
}
return result;
}
};
统一迭代法
思路
统一处理、访问两件事。在待处理的结点后面放入一个NULL指针作为标记。
- 根结点入栈
- 如果栈不空，循环：
- 如果结点非空，栈顶结点弹出，（判断非空后）依次放入右、中（同时放入NULL作为标记）、左结点。
复杂度分析
时间复杂度：O(N)
空间复杂度：O(N)
注意点
略
代码实现
/**
* 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> result;
stack<TreeNode*> st;
if(root != NULL)
st.push(root);
while(!st.empty()){
TreeNode* node = st.top(); st.pop();
if(node != NULL){
// 右中左
if(node->right) st.push(node->right);
st.push(node); st.push(NULL); // 当前结点打标记
if(node->left) st.push(node->left);
}else{
result.push_back(st.top()->val); st.pop();
}
}
return result;
}
};