赞
踩
首先先说下解题中常遇到的二叉树种类:
C++中map、set、multiset、multimap的底层实现都是平衡二叉搜索树(红黑树),所以map、set的增删操作时间复杂度是logn,注意unordered_map、unordered_set底层实现是哈希表。
Python中dict和set都是通过哈希表实现的,唯一不同的在于hash函数操作的对象,对于dict,hash函数操作的是其key,而对于set是直接操作的他的元素。假设操作内容为x,其作为因变量,放入hash函数,通过运算后取list的余数,转化为一个list的下标,此下标位置对于set而言用来放其本身,而对于dict而言则是创建了两个list,一个list放下标的key,一个放下标key对应的value。
然后再是二叉树的存储方式:
链式存储
顺序存储
最后来到本文的重点二叉树的遍历方式。
迭代版本:
前序遍历
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
if(root==nullptr) return res;
stack<TreeNode*> st;
st.push(root);
while(!st.empty()){
TreeNode* node = st.top();
st.pop();
res.push_back(node->val);
if(node->right) st.push(node->right);
if(node->left) st.push(node->left);
}
return res;
}
后序遍历只需要前序稍作修改即可。
vector<int> postorderTraversal(TreeNode* root) { vector<int> res; if(root==nullptr) return res; stack<TreeNode*> st; st.push(root); while(!st.empty()){ TreeNode* node = st.top(); st.pop(); res.push_back(node->val); if(node->left) st.push(node->left); if(node->right) st.push(node->right); } reverse(res.begin(),res.end()); return res; }
中序遍历
vector<int> inorderTraversal(TreeNode* root) { vector<int> res; if(root==nullptr) return res; stack<TreeNode*> st; TreeNode* curr = root; while(!st.empty()|| curr!=nullptr){ if(curr){ st.push(curr); curr=curr->left; }else{ curr = st.top(); st.pop(); res.push_back(curr->val); curr = curr->right; } } return res; }
层序遍历需要借助一个辅助数据结构即队列来实现。队列先进先出,符合一层一层遍历的逻辑,而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。
vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> res; if(root==nullptr) return res; queue<TreeNode*> que; que.push(root); while(!que.empty()){ int size = que.size(); vector<int> vec; for(int i=0;i<size;i++){ TreeNode* node = que.front(); que.pop(); vec.push_back(node->val); if(node->left) que.push(node->left); if(node->right) que.push(node->right); } res.push_back(vec); } return res; }
morris遍历是二叉树遍历算法的超强进阶算法,morris比那里可以将非递归遍历中的空间复杂度降为O(1)。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。