一、前序遍历非递归
力扣链接：力扣第144题：前序遍历
解析：
我们的思路是这样的：递归的本质其实就是一层一层的栈帧。我们要使用非递归，就得模拟这种栈帧，所以我们需要一个栈。这个栈专门存储结点，我们可以定义一个cur指针，先让他指向root。由于是先序遍历，所以我们需要将cur的所有左树结点都直接存入栈里面，并且我们还要顺便将里面的值给放入数组中，然后接下来我们就取出栈顶的结点，然后让cur指向右子树即可。这样循环下去就可以了
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> v; stack<TreeNode*> st; TreeNode* cur = root; while(cur || !st.empty()) { while(cur) { v.push_back(cur->val); st.push(cur); cur = cur->left; } TreeNode* top =st.top(); st.pop(); cur = top->right; } return v; } };
除了上面的方式以外，由于是先序遍历，所以可以先访问根节点，然后先访问右子树，然后访问左子树，依次放入栈里面，不过这种方法并不适合中序与后序。因为会陷入死循环。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<int> preorderTraversal(TreeNode* root) { if(root == nullptr) { return {}; } vector<int> v; stack<TreeNode*> st; st.push(root); while(!st.empty()) { TreeNode* top = st.top(); v.push_back(top->val); st.pop(); if(top->right) { st.push(top->right); } if(top->left) { st.push(top->left); } } return v; } };
二、中序遍历非递归
力扣链接：力扣第94题：二叉树的中序遍历
解析：
这道题与前序遍历是非常相似的，只需要改变结点进入顺序表的时机即可。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<int> inorderTraversal(TreeNode* root) { vector<int> v; stack<TreeNode*> st; TreeNode* cur = root; while(cur||!st.empty()) { while(cur) { st.push(cur); cur = cur->left; } TreeNode* top = st.top(); st.pop(); v.push_back(top->val); cur = top->right; } return v; } };
三、后序遍历非递归
力扣链接：力扣第145题：二叉树的后序遍历
解析：
这道题的麻烦之处，在于如何区分访问根节点还是往右子树走。
我们可以设置一个变量记录之前访问的右子树结点。
如果我们现在要访问的结点，它的右子树正好访问过，那么说明这个结点已经到了访问根节点的地步。
如果当前访问的右子树为空，说明已经到头了，需要访问这个结点了。
如果都不满足，那么就说明还需要继续访问右子树才可以。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<int> postorderTraversal(TreeNode* root) { vector<int> v; stack<TreeNode*> st; TreeNode* cur = root; TreeNode* prev = nullptr; while(cur||!st.empty()) { while(cur) { st.push(cur); cur = cur->left; } TreeNode* top = st.top(); if(top->right == nullptr||top->right == prev) { prev = top; v.push_back(top->val); st.pop(); } else { cur = top->right; } } return v; } };
