非递归的思路。
个人感觉这句话很有用。
本质上是在模拟递归,因为在递归的过程中使用了系统栈,所以在迭代的解法中常用Stack来模拟系统栈。
中序遍历
左根右,在递归的时候,如果当前节点有左子树,我们就递归左子树,然后输出中间节点,然后递归右子树。
我们用stack模拟这个操作。
使用cur来调度当前的节点,而不是仅用stack。
vector<int> inorderTraversal(TreeNode* root) {
if(!root) return {};
stack<TreeNode *> st;
TreeNode* cur = root;
vector<int>ans;
while(!st.empty() || cur){
while(cur){
st.push(cur);
cur = cur->left;
}
TreeNode* now = st.top();st.pop();
ans.push_back(now->val);
if(now->right){
cur = now->right;
}
}
return ans;
}
前序遍历
根左右。 可以方便的使用注释中给出的实现。为了统一三种非递归遍历的写法,这里仍然采用 cur来调度。
vector<int> preorderTraversal(TreeNode* root) {
// 迭代版。用stack,
// vector<int>ans;
// stack<TreeNode*>st;
// if(root!= NULL) st.push(root);
// while(!st.empty()){
// TreeNode* top = st.top();st.pop();
// ans.push_back(top->val);
// if(top->right) st.push(top->right);
// if(top->left) st.push(top->left);
// }
vector<int>ans;
stack<TreeNode*>st;
TreeNode* cur = root;
while(!st.empty() || cur){
while(cur){
ans.push_back(cur->val);
st.push(cur);
cur=cur->left;
}
TreeNode* now = st.top();st.pop();
if(now->right){
cur = now->right;
}
}
return ans;
}
后序遍历
后序遍历由前序遍历更改而来。 前序遍历是 根左右。 后序遍历是 左右根 = reverse(根右左)。
vector<int> postorderTraversal(TreeNode* root) {
vector<int>ans;
TreeNode* cur = root;
//后序遍历由前序遍历更改而来。 前序遍历是 根左右。 后序遍历是 左右根 = reverse(根右左)。
stack<TreeNode*> st;
while(!st.empty() || cur){
while(cur){
ans.push_back(cur->val);
st.push(cur);
cur = cur->right; // 先右
}
TreeNode* now = st.top();st.pop();
if (now->left) cur = now->left; // 后左
}
reverse(ans.begin(), ans.end());
return ans;
}
参考链接
https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/er-cha-shu-hou-xu-fei-di-gui-bian-li-liang-chong-z/