关于二叉树三种遍历的递归/非递归实现

以下算法实例中，二叉树定义如下：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

遍历完成的序列存储在vector

前序遍历

递归

class Solution {
public:
    vector<int> pre;// 存放完成遍历的序列
    vector<int> preorderTraversal(TreeNode* root) {
        if(root){
            // 按照 根->左->右 的顺序遍历
            pre.push_back(root->val);
            preorderTraversal(root->left);
            preorderTraversal(root->right);
        }
        return pre;
    }
};

按照根->左->右的遍历顺序，递归代码的可读性是显而易见的。

非递归(迭代)

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> pre;// 存放完成遍历的序列
        stack<TreeNode*> s;// 辅助栈
        s.push(root);
        TreeNode* ptr = NULL;
        while(!s.empty()){
            ptr = s.top();  // 指针指向栈顶元素，表示当前处理结点.
            s.pop();        // 出栈，表示经过本次循环，该结点处理完成.
            if(ptr){        // 若当前结点为空，则不作操作.
                pre.push_back(ptr->val);// 根结点入结果，完成根->左->右中“根”操作.
                s.push(ptr->right);     // 右孩子入栈.
                s.push(ptr->left);      // 左孩子入栈.
                /* 在栈访问到当前ptr指向的结点的孩子结点时，按照栈先入后出的特性，
                   会先对左孩子进行处理，再对右孩子进行处理，
                   完成了根->左->右中“左->右”操作. */
            }
            ptr = NULL;
        }
        return pre;
    }
};

非递归代码用到了栈结构辅助遍历，因为要服从根->左->右的遍历顺序，所以初始化从根节点开始，首先将根节点入栈，后进入while循环。

while循环的退出条件是辅助栈为空，即树遍历完，二者的等价性是显然的。

观察while循环内部的代码，参考注释，ptr每指向一个非空结点，就会完成以下操作：

根节点入结果
右孩子入栈
左孩子入栈

特别地，无论该结点左右孩子是否为空，都遵循这一操作，每当ptr指向空结点的时候，即为递归遍历中$if(root)$判断失败的时候。

结合递归代码，找出迭代中每一步对应着递归算法的哪一步，能帮助理解。

中序遍历

递归

class Solution {
public:
    vector<int> in;
    vector<int> inorderTraversal(TreeNode* root) {
        if(root){
            inorderTraversal(root->left);
            in.push_back(root->val);
            inorderTraversal(root->right);
        }
        return in;
    }
};

按照左->根->右的遍历顺序，不加赘述。

非递归(迭代)

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> in;
        stack<TreeNode*> s;
        TreeNode* ptr = root;
        while(ptr || !s.empty()){
            while(ptr){
                s.push(ptr);
                ptr = ptr->left;
            }
            // 服从左->根->右的遍历顺序.
            ptr = s.top();  // 指针指向栈顶元素，表示当前处理结点.
            s.pop();        // 出栈，表示经过本次循环，该结点处理完成.
            // 值得注意，ptr指向结点出栈后，当前栈顶元素即为ptr的“根”结点.
            if(ptr){        // 若当前结点为空，则不作操作.
                in.push_back(ptr->val); // 根结点入结果，完成左->根->右中“左”操作.
                ptr = ptr->right;       // ptr指向当前结点的右结点，完成“右”操作.
            }
        }
        return in;
    }
};

与前序遍历有所不同，开始时，ptr指向根节点，服从左->根->右的遍历顺序。

参考代码，最外层while循环加入了触发条件ptr，是为了初始时s为空服务的。

进入最外层while循环后，要将当前ptr所指向结点左孩子以及左孩子的左孩子...以此类推，依此压栈（即内层while循环），结合代码理解。

在退出内层while循环后，栈顶元素即为需要遍历的树最深且最“左”的结点，它没有左孩子（可能有右孩子，所以不一定是叶子结点）；结合代码，进入$if（ptr）$判断后，直接将它入结果，实际上，可以认为已经完成了左->根->右中的“左”操作和“根”操作，而“左”操作是一次空操作。

中序遍历的理解需要足够的抽象思维，每一次的“左”操作，是对当前结点的左孩子进行访问，同时也是该左孩子作为一棵“子树”进行中序遍历的操作。并且顺序如下：

$Node\Rightarrow visit Node\rightarrow left \Rightarrow inorderTraversal(Node\rightarrow left)$

其中 $visit Node\rightarrow left $ 只是一条指令，并不会直接将$Node\rightarrow left$ 的值入结果。$Node\rightarrow left$ 的值会在$inorderTraversal(Node\rightarrow left)$中入结果。

后序遍历

递归

class Solution {
public:
    vector<int> post;
    vector<int> postorderTraversal(TreeNode* root) {
        if(root){
            postorderTraversal(root->left);
            postorderTraversal(root->right);
            post.push_back(root->val);
        }
        return post;
    }
};

按照左->右->根的遍历顺序，不加赘述。

非递归(迭代)

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> post;
        stack<TreeNode*> s;
        s.push(root);
        while(!s.empty()){
            TreeNode* ptr = s.top();
            s.pop();
            if(ptr != NULL){
                post.push_back(ptr->val);
                s.push(ptr->left);
                s.push(ptr->right);
                // 与前序遍历相反，先压入左孩子，再压入右孩子；
                // 实际上完成了按照“根->右->左”顺序的遍历.
            }
        }
        reverse(post.begin(), post.end());
        // 后序遍历服从左->右->根的遍历顺序，post记录了根->右->左顺序的遍历；
        // 将post反转，即可得到后序遍历序列.
        return post;
    }
};

原本后序遍历的非递归实现较为复杂，以上提供一种巧妙的实现方法。

考虑后序遍历服从左->右->根的遍历顺序，建立一种新的遍历模式，即按照根->右->左的顺序遍历，正与后序遍历相反，因此，在完成遍历后将结果反转，即可得到后序遍历序列。

简单证明方法的正确性：

设n为结点数；

当n==0，满足；
当n==1，满足；
当n==2，根结点(a)及其左/右孩子(b)，
- 根->右->左的顺序遍历：ab;
- 后序遍历：ba;
- 满足。
当n==3，根结点(a)及其左孩子(b)，右孩子(c)，
- 根->右->左的顺序遍历：acb;
- 后序遍历：bca;
- 满足。
当n更大时，分成若干个部分，每个小部分满足$n\le3$的情况，显然，拼接后仍然满足情况。

以上总结了二叉树三种遍历的递归/非递归实现，作笔记用；

若文中内容有纰漏、错误，望斧正。

// Szp 2018/11/27

Karly