二叉树的遍历在算法题目中遇到的比较多,递归是最直观的写法,简洁明了,当然若是能掌握非递归以及Morris遍历就更好。网上关于这方面的文章很多,本文作为我自己的学习记录。

介绍

数据结构

二叉树是一个节点最多有两个子节点的“树”。本文采用Leetcode最常用的二叉树数据结构的定义,以C++实现。

// 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 {
public:
    vector<int> preorderTraversal(TreeNode *root) {
        if (!root) return ret;
        ret.push_back(root -> val);
        preorderTraversal(root -> left);
        preorderTraversal(root -> right);
        return ret;
    }
private:
    vector<int> ret;
};

中序

访问根节点 -> 递归访问左孩子 -> 递归访问右孩子。

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

后序

递归访问左孩子 -> 递归访问右孩子 -> 访问根节点。

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

非递归

非递归的写法以模拟递归为主。

前序

每次从栈中取出节点访问,同时入栈其右节点、左节点,这样左节点先于右节点出栈。

class Solution {
public:
    vector<int> preorderTraversal(TreeNode *root) {
        if (!root) return ret;
        stack<TreeNode *> s;
        s.push(root);
        while(!s.empty()) {
            TreeNode *node = s.top();
            s.pop();
            ret.push_back(node -> val);
            if (node -> right) s.push(node -> right);
            if (node -> left) s.push(node -> left);
        }
        return ret;
    }
private:
    vector<int> ret;
};

中序

先递归访问左孩子,等同于先找到当前子树(包括整棵树)的最左子节点,找到后访问它,然后访问它的右子树,对于右子树是同样的规则,先访问右子树的最左节点。具体参考代码。

class Solution {
public:
    vector<int> inorderTraversal(TreeNode *root) {
        if (!root) return ret;
        stack<TreeNode *> s;
        TreeNode *node = root;
        while(!s.empty() || node) {
            if (node) {
                s.push(node);
                node = node -> left;
            }
            else {
                TreeNode *temp = s.top();
                s.pop();
                ret.push_back(temp -> val);
                node = temp -> right;
            }
        }
        return ret;
    }
private:
    vector<int> ret;
};

后序

方法1

Postorder需先拜訪左右子節點,最後拜訪父節點。遍歷每個節點時,將父節點和左右子節點都放進stack中,並將父節點的左右子節點設為NULL。當stack pop出一個節點沒有左右子節點時,表示他的左右子節點已經被拜訪過了,則可以拜訪父節點。

这个方法改变了原本树的结构。

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
       vector<int> res;
        if (!root) return res;
        stack<TreeNode*> s;
        s.push(root);
        while (!s.empty()) {
            TreeNode *node = s.top();
            if (!(node -> left) && !(node -> right)) {
                res.push_back(node -> val);
                s.pop();
            }
            if (node -> right) {
                s.push(node -> right);
                node -> right = nullptr;
            }
            if (node -> left) {
                s.push(node -> left);
                node -> left = nullptr;
            }
        }
        return res;
      
    }
};

方法2

引入一个prev指针,标记访问序列中前一个二叉树节点,如果root->right即为prev,或者root->right为NULL,就可以判断已经从右子树访问返回。
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
       vector<int> res;
        if (!root) return res;
        stack<TreeNode*> s;
        TreeNode *cur = root, *prev = nullptr;
        while (cur || !s.empty()) {
            if (cur) {
                s.push(cur);
                cur = cur -> left; 
            }
            else {
                TreeNode *temp = s.top();
                if (!(temp -> right) || temp -> right == prev) {
                    res.push_back(temp -> val);
                    prev = temp;
                    s.pop();
                    cur = nullptr;
                }
                else cur = temp -> right;
            }
        }
        return res;   
    }
};

层序

非常直观,采用BFS即可。

class Solution {
public:
    vector<vector<int> > levelOrder(TreeNode* root) {
        if(!root) return {};
        queue<TreeNode*> q;
        q.push(root);
        vector<vector<int> > res;
      
        while(!q.empty()){
            int sz = q.size();
            vector<int> tmp;
            for(int i = 0; i < sz; i++){
                TreeNode* t = q.front();
                q.pop();
                tmp.push_back(t -> val);
                if(t -> left) q.push(t -> left);
                if(t -> right) q.push(t -> right);
            }
            res.push_back(tmp);
            tmp.clear();
        }
        return res;
    }
};

Morris 遍历

刚才的递归和非递归解法,因栈空间,空间复杂度是O(n),那么 Morris 遍历通过临时对子节点的修改来实现“后继”节点的保存,之后再次遍历到时可以恢复树的结构,以此仅仅通过O(1)的空间实现树的遍历,这是KMP算法里面的Morris发明的。下面以中序遍历为例,简单说说它的过程。

下面的内容来自第三篇和第四篇参考文章,待我慢慢吃透。

Morris中序遍历

找到左子树上最右节点,将其右指针和当前根节点连接起来

以root = [5,3,6,2,4,null,8,1,null,null,null,7,9]为例,将4的右指针指向cur

morris1

morris2

从根节点向左,每个新的根节点都重复第一步。最终到达如下图的状态:

morris3

当cur的左子树遍历完成后,向右子树遍历, 这里要了解左子树完成遍历的情况:

  1. 当cur的左指针为空时,比如图中的1节点(左指针为空),这时候就必须向右走,回到2节点。
  2. 第二种是当cur的左子树上最右节点指向cur时(说明之前已经连接过了,这是遍历过一遍左子树又走回来了)

将左子树最右节点的右指针重置为空即可,如下图过程。

morris3

morris4

morris5

morris6

morris7

morris8

则遍历代码:

public void morrisInOrderTraversal(TreeNode root) {
    TreeNode node = root, prev = null; // 仅存放两个临时变量,O(1)空间复杂度
    while (node != null) { // 当前节点为空时,说明访问完成
        if (node.left == null) { // 左子树不存在时,访问+进入右节点
            visit(node);
            node = node.right;
        }
    else { // 左子树存在,寻找前驱节点。注意寻找前驱节点时,会不断深入右子树。不加判断时,若前驱节点的右子树已指向自己,会引起死循环
            prev = node.left;
            while (prev.right != null && prev.right != node) prev = prev.right;
            if (prev.right == null) { // 前驱节点未访问过,存放后继节点
                prev.right = node;
                node = node.left;
            } else { // 前驱节点已访问过,恢复树结构
                visit(node); // 确定访问过左子树后,访问当前节点
                prev.right = null;
                node = node.right;
            }
        }
    }
}

复杂度分析

空间复杂度为 O(1),显而易见。

时间复杂度为 O(n)。例如对于一棵节点数为n的满二叉树,其倒数第二层的节点树为n/4,寻找前驱的长度为1,以此类推,我们可以得到找前驱节点的经过的节点数.

$$ C = 2 \times \sum_{i=1}^{\log_2(n/2)} \frac{n}{2^{i+1}} \times i = 2 \times \left( \frac{n}{4} \times 1 + \frac{n}{8} \times 2 + \frac{n}{16} \times 3 + \cdots + 1 \times \log_2(\frac{n}{2}) \right) = 2 \times ( n - 1 - \log_2(n) ) \sim O(n) $$

如图所示:

Morris前序遍历与后序遍历算法

介绍完了Morris中序遍历,其先序遍历和后序遍历都是在中序遍历的基础之上加以改动得到的。例如先序遍历时,需要先访问节点,再决定深入左子树或右子树:

public void morrisPreOrderTraversal(TreeNode root) {
    TreeNode node = root, prev = null; // 仅存放两个临时变量,O(1)空间复杂度
    while (node != null) { // 当前节点为空时,说明访问完成
        if (node.left == null) { // 左子树不存在时,访问+进入右节点
            visit(node);
            node = node.right;
        } else { // 左子树存在,寻找前驱节点。注意寻找前驱节点时,会不断深入右子树。不加判断时,若前驱节点的右子树已指向自己,会引起死循环
            prev = node.left;
            while (prev.right != null && prev.right != node) prev = prev.right;
            if (prev.right == null) { // 前驱节点未访问过,存放后继节点
                visit(node); // 在确定前驱节点未访问过时,访问当前节点(注意与中序遍历的区别)
                prev.right = node;
                node = node.left;
            } else { // 前驱节点已访问过,恢复树结构
                prev.right = null;
                node = node.right;
            }
        }
    }
}

后序遍历相比中序遍历稍微复杂一些,但是后序遍历也有其特性:若一个节点是右孩子,或该节点是左孩子但是没有兄弟节点,则访问完该节点后立刻会访问该节点的父节点。

推广到Morris遍历里,可以得到:当访问到任何节点C的前驱节点B时,由B到C的路径(不包括节点C)即为之后的访问顺序。

因此所有的访问过程可以化为由B到C的访问。得到的Morris后序遍历程序如下,注意为了保证程序能够顺利访问右子树,为根节点添加了一个哨兵节点:

public void morrisPostOrderTraversal(TreeNode root) {
    TreeNode temp = new TreeNode(new Value(Value.INVALID_VALUE)), node = temp, prev = null; // 仅存放一个“哨兵”节点和两个临时变量,O(1)空间复杂度
    temp.left = root;
    while (node != null) { // 当前节点为空时,说明访问完成
        if (node.left == null) { // 左子树不存在时,进入右节点
            node = node.right;
        } else { // 左子树存在,寻找前驱节点。注意寻找前驱节点时,会不断深入右子树。不加判断时,若前驱节点的右子树已指向自己,会引起死循环
            prev = node.left;
            while (prev.right != null && prev.right != node) prev = prev.right;
            if (prev.right == null) { // 前驱节点未访问过,存放后继节点
                prev.right = node;
                node = node.left;
            } else { // 前驱节点已访问过,恢复树结构
                visitReverse(node.left, prev); // 确定访问过左子树后,逆序访问沿路节点(注意与中序遍历的区别)
                prev.right = null;
                node = node.right;
            }
        }
    }
}

对于逆序访问函数visitReverse(),我们可以采用链表翻转的方式实现,一个参考实现如下:

public void visitReverse(TreeNode node1, TreeNode node2) {
    reverse(node1, node2); // 首先进行翻转
    TreeNode node = node2; // 之后进行顺序访问
    while (node != node1) {
        visit(node);
        node = node.right;
    }
    visit(node1);
    reverse(node2, node1); // 恢复结构
}

public void reverse(TreeNode node1, TreeNode node2) {
    // 实现链表翻转
    TreeNode prev = node1;
    TreeNode current = prev.right;
    TreeNode next = current.right;
    while (prev != node2) {
        current.right = prev;
        prev = current;
        current = next;
        next = next.right;
    }
}

以此实现后序遍历结果。由于相比较其他两种遍历,后序遍历多了逆序访问的过程,其时间复杂度与链表长度成正比。因此后序遍历的时间复杂度仍然为O(n)。

参考

三種 Interative Binary Tree Traversal 的方法 (In-Order, Pre-Order and Post-Order) | Shubo 的程式教學筆記

数据结构与算法(一):二叉树的非递归遍历 - 知乎 (zhihu.com)

O(1)空间的Morris中序遍历解法 - 递增顺序搜索树 - (leetcode-cn.com)

经典算法小评(2)——Morris树遍历算法 (ghh3809.github.io)

最后修改:2022 年 04 月 11 日
如果觉得我的文章对你有用,请随意赞赏