解决四种二叉树遍历问题

vlambda
2021-02-17

解决四种二叉树遍历问题

这是 LvLin 的第 7 篇原创

今天在 LeetCode 上刷了几道二叉树遍历的算法题，做一个总结。

基本上所有二叉树相关的算法题，都需要对二叉树进行遍历。而常见的二叉树遍历方式主要分为前序、中序、后序遍历和层序遍历。以下图这棵二叉树进行简单讲解。

解决四种二叉树遍历问题

层序遍历很容易理解，就是一层层地来，像上图这棵树，进行层序遍历的结果就是【1，2，3，4，5，6，7】。

而前序、中序和后序遍历，这前、中、后指的是二叉树的根节点被取值的先后，节点左右两边节点则是严格按照先左后右的顺序。

层序遍历

对于二叉树的遍历，一般都有两种解法，递归和非递归。

LeetCode 第 102 题是关于二叉树层序遍历的题目。

利用递归的解法通常写起来比较容易，二叉树层序遍历的递归解法如下所示：

var levelOrder = function(root) {
    if (!root) return [];

    let result = [];
    function traversal(node, level) {
        if (!result[level]) result[level] = [];
        result[level].push(node.val);
        node.left && traversal(node.left, level+1);
        node.right && traversal(node.right, level+1);
    }
    traversal(root, 0);
    return result;
};

除了递归解法，也可以利用队列，通过循环的方式进行实现：

var levelOrder = function(root) {
    if (!root) return [];

    let result = [];
    let queue = [root];

    while(queue.length) {
        let arr = [];
        let len = queue.length;
        while(len) {
            let node = queue.shift();
            arr.push(node.val);
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);   
            len--;
        }
        result.push(arr);
    }

    return result;
};

前、中、后序遍历

拿上文示例的二叉树来说，前序遍历按照「中左右」顺序从根节点开始，遍历结果为【1，1节点左边子树，1节点右边子树】。对于 1 节点左边的子树，进行「中左右」顺序遍历的结果是【2，4，5】，对于 1 节点右边的子树，进行「中左右」顺序遍历的结果是【3，6，7】，最终得到的结果为【1，2，4，5，3，6，7】。

中序遍历则是按照「左中右」顺序从根节点开始，遍历结果为【1节点左边的子树，1，1 节点右边的子树】，对于 1 节点左边的子树，进行「左中右」顺序遍历的结果是【4，2，5】，对于 1 节点右边的子树，进行「左中右」顺序遍历的结果是【6，3，7】，最终得到的结果为【4，2，5，1，6，3，7】。

后序遍历就不多说了，遍历结果为【4，5，2，6，7，3，1】。

LeetCode 上第 94、144、145题分别是二叉树的中序、前序和后序遍历，也都分为递归解法和非递归解法两种。

我们先来看中序遍历的递归解法：

var inorderTraversal = function(root) {
    if (!root) return [];
    let arr = [];
    function traversal(node) {
        if (node.left) traversal(node.left);
        arr.push(node.val)
        if (node.right) traversal(node.right);
    };
    traversal(root);
    return arr;
};

通过函数 traversal 的递归调用实现了遍历。前序和后序遍历只是根节点的顺序不一样，那我们完全可以复用中序遍历的代码，将递归函数内的代码顺序调换一下即可。

前序遍历和后序遍历的 traversal 函数如下所示：

    //... 前序遍历
    function traversal(node) {
        arr.push(node.val)
        if (node.left) traversal(node.left);
        if (node.right) traversal(node.right);
    };
    //... 后序遍历
    function traversal(node) {
        if (node.left) traversal(node.left);
        if (node.right) traversal(node.right);
        arr.push(node.val)
    };

非递归解法，我们同样还是以中序遍历为例，利用了栈，通过循环实现：

var inorderTraversal = function(root) {
    if (!root) return [];

    let result = [];
    let stack = [root];
    let node;
    while(stack.length) {
        node = stack.pop();
        if (node) {
            node.right && stack.push(node.right);
            stack.push(node, null);
            node.left && stack.push(node.left);
        } else {
            result.push(stack.pop().val);
        }
    }
    return result;
};

同样的，前序遍历和后序遍历也是在这道题的基础上经过小幅改动就可以复用。对 while 循环中的代码进行改动，实现如下：

    // ... 前序遍历
    // 根节点不需要重新入栈，所以不需要进行判断
    while(stack.length) {
        let node = stack.pop();
        result.push(node.val);
        node.right && stack.push(node.right);
        node.left && stack.push(node.left);
    }
    // ...后序遍历
    while(stack.length) {
        let node = stack.pop();
        if (node) {
            stack.push(node, null);
            node.right && stack.push(node.right);
            node.left && stack.push(node.left);
        } else {
            result.push(stack.pop().val);
        }
    }