首先来复习一下三种遍历方式
所谓二叉树的遍历，是指按照一定的搜索路径将树的所有结点访问且仅访问一次。
按照根结点何时被访问，可以分为先序、中序和后序三种遍历算法.
主要区别在于 root 节点什么时候被访问.
先序：访问根结点，先序遍历左子树，先序遍历右子树
中序：中序遍历左子树、访问根结点、中序遍历右子树
后序：后序遍历左子树、后序遍历右子树、访问根结点
image.png
先序
https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
递归
class Solution {
public:
vector<int> res;
vector<int> preorderTraversal(TreeNode* root) {
if (!root) return res;
res.push_back(root->val);
preorderTraversal(root->left);
preorderTraversal(root->right);
return res;
}
};
非递归
思路：
首先访问当前树的根结点数据，接下来应该依次遍历其左子树和右子树，然而程序的控制流只能处理其一，所以考虑将右子树的根保存在栈里面，当前指针则指向需先处理的左子树，为下次循环做准备；若当前指针指向的树为空，说明当前树为空树，不需要做任何处理，直接弹出栈顶的子树，即遍历右子树。
伪代码
void preOrder(TreeNode root)
{
Init(stack);
//tips:初始栈压入一个null，pop的时候就不用对这个栈判空了
stack.push(null);
while( root != null )
{
visit(root);
if(root.right != null) stack.push(root.right);
if(root.left != null) root = root.left;
else root = stack.pop();
}
}
代码
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> res;
st.push(NULL);
while (root) {
res.push_back(root->val);
if (root->right) st.push(root->right);
if (root->left) root = root->left;
else {
root = st.top();
st.pop();
}
}
return res;
}
};
总结
- 由于是先访问根节点，再遍历左子树，因此root = root.left的同时要把root.right存到栈里，还不能遍历右子树，因为左子树还没有遍历完（左子树为null）。所以，直到root.left == null的时候，才可以遍历右子树（root = stack.pop()）。
stack在pop前要判断这个栈是否为空：stack.isEmpty() - 不想显式地写这个判断的话，可以使用一个tip：初始化栈的时候push进去一个null值。这样就可以直接pop了，如果栈为空了，pop出来一个null值，正好。
- visit（root）的含义视情况而定。可以为打印（对于函数返回值为void）。
本题为返回一个list，所以visit(root)的含义是list.add(root)。 - 注意C++中stack，其中有两个方法：
pop(), 返回void,
top(),返回栈顶的引用。
所以想要提取栈顶元素，直接用s.top()
中序
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> st;
while (root || !st.empty()) {
if (root) {
st.push(root);
root = root->left;
} else {
root = st.top();
res.push_back(root->val);
st.pop();
root = root->right;
}
}
return res;
}
};
后序
这个改天再自己做一下，大致意思写对了，小细节没写对，导致死循环。我也懒得debug了直接照着答案改了。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> st;
TreeNode* r;//记录刚访问过的节点
while (root || !st.empty()) {
if (root) {
st.push(root);
root = root->left;
}
// root为null 说明左孩子已经没得访问了，可能要访问右孩子，也可能右孩子也访问完了
else {
// 如果存在右孩子，而且右孩子不是上次最后访问的那个节点
// 那么说明root 的右孩子还没有访问，那么栈顶的右孩子置成 root, 继续遍历
TreeNode* tmp = st.top();
if (tmp->right && tmp->right != r) {
root = tmp->right;
} else {
// 其他情况，例如右孩子NULL，或者 右孩子是上次访问的节点（说明栈顶这个节点的右孩子已经访问过了）
// 那么直接访问栈顶这个节点即可，还要弹栈
res.push_back(tmp->val);
st.pop();
r = tmp; //记录刚访问过的节点
}
}
}
return res;
}
};
写了三种遍历方式之后，突然意识到，为什么非递归一定会用到栈？
我觉得是因为，二叉树的结构，父结点到子结点的指针是单向的，没有从子结点指向父结点的指针。因此如果从孩子结点回到父结点，只有一个办法就是弹栈。
好，回到正题。
后序遍历的顺序是"左子树->右子树->根"，它要求左子树和右子树都在根之前输出。
所以后序遍历序列有个特点，visit到某个结点时，其左右儿子一定刚刚被visit过（如果有儿子的话）。也就是说，父结点前面紧挨着的一定是儿子结点（如果有的话）。
image.png
后序：b c a
而从整体来看，后序遍历是从下往上遍历的。怎么理解呢？就是假设当前访问的是a，那么b,c子树一定都被访问过了。也就是a的下层所有结点都已经被访问过了。
假设当前访问到b，那么说明b子树已经遍历过了，下面要遍历b的右兄弟，如何从b到c呢？显然是b->a然后a->c。即依赖b的父结点作为桥梁。
当访问某个结点p时，栈中的结点恰好是p的所有祖先。
所以访问完b之后，要指向a，a在哪里？在栈顶。
此时不要立刻访问a，而是要看看a还有没有右子树，毕竟左右子树都遍历完成之后才可以访问根结点a。所以不要弹栈，而是p = top()去让p指向a，看看a.right是否存在并且没访问过。
用栈来存储结点，必须分清返回根结点时（s.top()），是从左子树返回的，还是从右子树返回的。因此用一个辅助指针r指向一个最近访问过的结点。
例如，访问完b之后，r = b纪录一下, p = top()查看栈顶，然后看p.right是否存在并且p.right是否不等于r，发现c != b，ok可以继续遍历右子树c。
右子树c遍历完成的标志事件是访问c，这个时候你不知道c是不是父结点的右儿子呀，所以p = top(), 然后看看p.right是否存在并且等于c，发现等于，说明右子树已经遍历过了，此时可以访问根结点了，弹栈吧。
还有颜色标记法 据说很简单 值得研究
https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/yan-se-biao-ji-fa-yi-chong-tong-yong-qie-jian-ming/
网友评论