二叉树的遍历
二叉树的递归遍历
递归三要素：
- 确定递归函数的参数和返回值：
void preorder(TreeNode *root, vector<int>& res)
- 确定终止条件：
if(cur == nullptr) return;
- 确定单层递归的逻辑
时间复杂度：O(n)
空间复杂度：O(n)
class Solution { public: void preorder(TreeNode *root, vector<int> &res) { if (root == nullptr) return; res.push_back(root->val); //中 preorder(root->left, res); //左 preorder(root->right, res); //右 } vector<int> preorderTraversal(TreeNode *root) { vector<int> res; preorder(root, res); return res; } };
实现不同的遍历顺序通过修改单层递归的逻辑实现
二叉树的迭代遍历
通过栈实现
时间复杂度：O(n)
空间复杂度：O(n)
前序遍历
class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> s; if(root == nullptr) return res; s.push(root); //压入根结点 while (!s.empty()){ //入栈是 根右左 TreeNode* node = s.top(); s.pop(); res.push_back(node->val); //中 if (node->right) stk.push(node->right); //右 if (node->left) stk.push(node->left); //左 } return res; } };
中序遍历
class Solution { public: vector<int> inorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> s; TreeNode* cur = root; while (cur != NULL || !st.empty()) { if (cur != NULL) { // 指针来访问节点，访问到最底层 s.push(cur); // 将访问的节点放进栈 cur = cur->left; // 左 } else { cur = s.top(); // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据） s.pop(); res.push_back(cur->val); // 中 cur = cur->right; // 右 } } return res; } };
后序遍历
class Solution { public: //后续迭代最难，有些结点反复进出栈 vector<int> postorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> s; if (root == nullptr) return res; s.push(root); while(!s.empty()){ auto node = s.top(); s.pop(); res.push_back(node->val); //中 if(node->left) s.push(node->left); //左 if(node->right) s.push(node->right); //右 } reverse(res.begin(), res.end()); // 将结果反转之后就是左右中的顺序了 return res; } };
二叉树的层序遍历
通过队列实现
class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { vector <vector <int>> res; if (!root) return res; //排除空二叉树情况 queue <TreeNode*> q; q.push(root); //根结点入队 while (!q.empty()) { int currentLevelSize = q.size(); //记录当前层的结点个数 res.push_back(vector <int>()); for (int i = 1; i <= currentLevelSize; ++i) { auto node = q.front(); //获取队头元素 q.pop(); //删除队头元素 res.back().push_back(node->val); //往ret的最后一个容器中压元素 if (node->left) q.push(node->left); if (node->right) q.push(node->right); } } return res; } };
