链接: https://leetcode-cn.com/problems/binary-tree-postorder-traversal/description/
题意
解法
同样学习一手后序遍历的非递归写法
使用到的第一种解法是利用前序遍历的反向写法
先将左子树入栈 再将右子树入栈
最后将结果反转就是后序遍历序列
代码
1 | class Solution { |
统一版
在看题解的时候,看到一个很妙的解法,将三种不同的遍历方式进行统一
访问到节点的时候将一个nullptr入栈作为标记
利用一个nullptr节点判断当前节点是否被访问过
访问过就会在下次遇到nullptr的时候进行输出
前中后遍历统一版迭代写法(只用移动左中右的顺序即可)
前序遍历
1 | vector<int> preorderTraversal(TreeNode* root) { |
中序遍历
1 | vector<int> inorderTraversal(TreeNode* root) { |
后序遍历
1 | vector<int> postorderTraversal(TreeNode* root) { |