中序
中序感觉比较好理解，就先写了。我们知道，对于中序遍历，就是将二叉树的所有结点“从左到右”投影到水平线上的顺序。具体如下所示，故这颗树的中序遍历为：3,6,8,5,1,9,0,2。
图1. 中序遍历示意图
有了这一层概念之后，再加上二叉树天然的递归性质，我们不难得出结论：对于任意的二叉树，中序遍历得到的第一个结点，永远是这颗二叉树最左下的那一个结点。对于上图而言，也就是结点3。
然后我们需要知道的是，哪些子树是需要遍历的，显然，对于上图而言，1、8、6、3，它们都是某颗子树的根节点，我们都需要记录下来，很明显，这是先进后出的顺序，我们需要一个栈。
遍历完结点3之后，我们需要做什么呢？将根节点设置为当前结点的右孩子结点！这一步很重要。我们不妨拿结点8来示例。结点8被访问并且记录了值以后，我们下一个需要遍历的是结点5，也就是其右子树。前面已经说过，树是有递归性质的，因此，我们将根节点设置为结点5，并重新找到这颗子树的最左下的结点，访问，转置它的右子树，如此往复，直至结束。
具体的代码如下：
/**
* 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 {
stack<TreeNode *> Q;
void deepInLeftBr(TreeNode *root){
for(auto head = root; head; head=head->left){
Q.push(head);
}
}
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
auto head = root;
while(true){
deepInLeftBr(head);
if(Q.empty()) break;
auto tmp = Q.top();
Q.pop();
ans.push_back(tmp->val);
head = tmp->right;
}
return ans;
}
};
后序
有了中序的基础，后序遍历就简单很多了。虽然后序序列不像中序那样直接把结点进行投影就可以得到，但从“左右中”这个特点出发，我们还是可以得知：对于任意的二叉树，后序遍历时，第一个访问到的结点依旧是最左下的结点，所以中序代码中的deepInLeftBr函数依旧会用到。
接下来就是关键点了，而这也是中序和后序最大的不同点。因为在后序遍历中，根节点在最后才会被访问到，所以我们需要一个机制，用来判断根节点的右子树是否已经被访问完毕。这里就又是一个“递归”的思想了：因为右子树最后被访问到的结点依旧是右子树的根节点，也就是当前根节点的右孩子结点，所以我们可以设立一个prev指针，每当访问了一个结点之后，就将prev设置为该结点，如此一来，我们就可以通过计算root->right == prev是否为真，来判断根节点的右子树是否已经被访问完毕。
如果能够想通上面这一段话的内涵，那么写出对应的迭代版本的代码就不是难事了。
/**
* 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 {
stack<TreeNode *> S;
void deepInLeftBr(TreeNode *head){
for(auto ptr = head; ptr; ptr = ptr->left){
S.push(ptr); // only non-empty pointer can be pushed into stack;
}
}
public:
vector<int> postorderTraversal(TreeNode* root) {
if(!root) return {};
TreeNode *head = root, *prev = nullptr;
vector<int> ans;
while(true){
deepInLeftBr(head);
if(S.empty()) break;
head = S.top();
S.pop();
if(head->right==nullptr || head->right==prev){ // right sub-tree has been visited already;
ans.emplace_back(head->val); // visiting the root node;
prev = head; // mark!!!
head = nullptr; // avoid dead-circle because of deepInLeftBr();
} else { // right sub-tree hasn't been visited, so we should push the root node again,
// and give the control power to right sub-tree
S.push(head);
head = head->right;
}
}
return ans;
}
};
前序
有了中序和后序遍历的经验，现在我们再来思考前序遍历。从“中左右”我们可以知道，对于任意的二叉树，在前序遍历时，首先都是沿着左下方向去遍历这条直线上的元素。拿上面的图1中的二叉树为例，首先遍历到的元素为：1、8、6、3。
想通了这一点之后，我们接下来再观察，左下方向的直线被访问完了之后，又该访问哪里呢？不难发现，接下来应该访问最近的一颗非空右子树。以图1为例，当1、8、6、3被访问完了以后，接下来应该依次访问以5为根节点的子树，以0为根节点的子树。当然，这就需要我们在访问左下直线的过程之中，用栈来保存出现过的非空右子树结点。
ok，大功告成，代码也就出来了。
/**
* 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 {
stack<TreeNode *> S;
vector<int> ans;
void visitLeftBr(TreeNode *head){
for(auto ptr = head; ptr; ptr = ptr->left){
ans.push_back(ptr->val);
if(ptr->right)
S.push(ptr->right);
}
}
public:
vector<int> preorderTraversal(TreeNode* root) {
if(!root) return {};
auto head = root;
while(true){
visitLeftBr(head); // visit nodes at left-down direction, and record right sub-tree at same time
if(S.empty()) break;
head = S.top();
S.pop();
}
return ans;
}
};
网友评论