二叉树理论基础
二叉树种类：
1. 满二叉树
如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。节点数量2^k-1,k是深度。
2. 完全二叉树
在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。比如优先级队列实际上是堆，堆即为完全二叉树，同时保证父子节点顺序关系。
3.二叉搜索树(logn)
二叉搜索树是一个有序树，对布局没要求，对顺序有要求。若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。
4.平衡二叉搜索树(AVL)
它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。插入是log(n)搜索也是log(n)。map和set的底层就是平衡二叉搜索树，因此元素有序。注意unordered_set或unordered_map是用哈希表实现。
二叉树存储方式
1.链式存储
用指针实现。通过左指针和右指针指向下一个子节点。
2.顺序存储
用数组实现。如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。
更常使用链式存储，但要清楚如何用数组实现。
二叉树的遍历方式
深度优先搜索：先一直往下遍历，直到触底进行回退，前中后序搜索都属于深度优先搜索。可以用递归法（用栈）或者迭代法（非递归，用队列）。
广度优先搜索：一层层或者一圈圈进行遍历，二叉树中层序遍历就是广度优先搜索。层序遍历就是迭代法，使用队列实现。
前序遍历：中左右
中序遍历：左中右
后续遍历：左右中
二叉树的定义方式
struct TreeNode{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) :val(x),left(NULL),right(NULL)
};
递归遍历
1.确认递归函数的参数和返回值
2.确定终止条件
3.确定单层递归的逻辑
前序遍历
void traversal(*cur,vector<int> &num){
if(cur==NULL)
return;
num.push_back(cur->val);
traversal(cur->left,num);
traversal(cur->right,num);
}
中序遍历
void traversal(*cur,vector<int> &num){
if(cur==NULL)
return;
traversal(cur->left,num);
num.push_back(cur->val);
traversal(cur->right,num);
}
后序遍历
void traversal(*cur,vector &num){
if(cur==NULL)
return;
traversal(cur->left,num);
traversal(cur->right,num);
num.push_back(cur->val);
}
完成了144.145.94三道分别是前后中序遍历的题目。
迭代遍历
前序遍历
前序遍历是中左右，使用stack先把中push，然后pop，再把右push，左push，这样弹出即为中左右。记得中间check一下node是否为null
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();
if(Node!=NULL)
{
result.push_back(Node->val);
st.push(Node->right);
st.push(Node->left);
}
}
return result;
}
后序遍历
后序遍历是左右中，可以在前序遍历的基础上，变成中右左，最后再reverse数组变成左右中。
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();
if(Node!=NULL)
{
result.push_back(Node->val);
st.push(Node->left);
st.push(Node->right);
}
}
reverse(result.begin(),result.end());
return result;
}
中序遍历
中序遍历是左中右，需要先一直到最底的左节点，直到左节点不存在，通过st.top()找到中间节点，取值弹出再接着遍历右节点。
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> result;
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;
}
统一迭代
统一迭代是通过在访问过的节点后放空指针的方式进行标记，暂时搁置。
