二叉树理论基础
二叉树的种类
- 满二叉树 | 完美二叉树：没有缺少的结点，叶子结点也全满
- 完全二叉树：只有最底层结点没满，但必须从左到右连续。（满二叉树是特殊的完全二叉树）
- 二叉搜索树:左小右大
- 平衡二叉搜索树: 左右子树的高度差 Δh <= 1
二叉树的存储方式:
- 链式存储：链表
- **顺序存储： **数组
二叉树的遍历:
- 深度优先遍历
- 前序遍历（递归法，迭代法）
- 中序遍历（递归法，迭代法）
- 后序遍历（递归法，迭代法）
- 广度优先遍历
- 层次遍历（迭代法）
- 前序遍历：中左右
- 中序遍历：左中右
- 后序遍历：左右中
二叉树的定义:
truct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
初始化列表： TreeNode(int x) : val(x), left(NULL), right(NULL) {}
二叉树的递归遍历
前序遍历
class Solution {
public:
//前序遍历,中左右
void traversal(TreeNode* cur, vector<int>& result){
if(cur == NULL) return;
result.push_back(cur->val);
traversal(cur->left, result);
traversal(cur->right, result);
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
traversal(root, result);
return result;
}
};
后序遍历
class Solution {
public:
//后序遍历,左右中
void traversal(TreeNode* cur, vector<int>& result){
if(cur == NULL) return;
traversal(cur->left, result);
traversal(cur->right, result);
result.push_back(cur->val);
}
vector<int> postorderTraversal(TreeNode* root){
vector<int> result;
traversal(root, result);
return result;
}
};
中序遍历
class Solution {
public:
//中序遍历,左中右
void traversal(TreeNode* cur, vector<int>& result){
if(cur == NULL) return;
traversal(cur->left, result);
result.push_back(cur->val);
traversal(cur->right, result);
}
vector<int> inorderTraversal(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> 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; //左
}
else{
cur = st.top();
st.pop();
result.push_back(cur->val); //中
cur = cur->right; //右
}
}
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()); //key step
return result;
}
};