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

以下算法实例中,二叉树定义如下:

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每指向一个非空结点,就会完成以下操作:

  1. 根节点入结果
  2. 右孩子入栈
  3. 左孩子入栈

特别地,无论该结点左右孩子是否为空,都遵循这一操作,每当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

11-28 05:06