递归算法
三要素
- 参数和返回值
- 终止条件
- 单层返回逻辑
例题
leetcode：
- 144.二叉树的前序遍历(opens new window)
- 145.二叉树的后序遍历(opens new window)
- 94.二叉树的中序遍历
迭代遍历
递归的本质还是利用栈实现的，所以我们可以配合栈来实现迭代遍历
前序遍历
先压入root；
root出栈时，压入右左节点，然后重复该过程直到栈空。
class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> res;stack<TreeNode*> Mysta;if(root)Mysta.push(root);while(!Mysta.empty()){TreeNode* cur=Mysta.top();Mysta.pop();if(cur->right)Mysta.push(cur->right);if(cur->left)Mysta.push(cur->left);res.push_back(cur->val);}return res;}};
中序遍历
中序遍历不能直接改编前序遍历；
把左边一支全部压栈；
然后吐出栈顶为cur，处理完后，将当cur的右节点以及左边的一支压入
class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> res;stack<TreeNode*> Mysta;TreeNode* cur=root;while(cur){Mysta.push(cur);cur=cur->left; }while(!Mysta.empty()){cur=Mysta.top();Mysta.pop();if(cur->right){TreeNode* tmp=cur->right;while(tmp){Mysta.push(tmp);tmp=tmp->left;}}res.push_back(cur->val);}return res;}
};
后序遍历
后序遍历可以通过镜像的先序遍历，然后反转整个结果得到。
class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> res;stack<TreeNode*> stack;if(root)stack.push(root);while(!stack.empty()){TreeNode* cur=stack.top();stack.pop();res.push_back(cur->val);if(cur->left)stack.push(cur->left);if(cur->right)stack.push(cur->right);}reverse(res.begin(),res.end());return res;}
};
统一迭代
层序遍历
队列