二叉树前中后序遍历非递归实现(JavaScript)

6,102 阅读3分钟

二叉树使用递归实现前中后序遍历是非常容易的,本文给出非递归实现前中后序遍历的方法,核心的思想是使用一个栈,通过迭代来模拟递归的实现过程

下面实现中root代表二叉树根节点,每个节点都具有left,right两个指针,分别指向当前节点左右子树,一个val属性代表当前节点的值

前序遍历(preorderTraversal)

const preorderTraversal = function(root) {
    const stack = [], res = []
    root && stack.push(root)
    // 使用一个栈stack,每次首先输出栈顶元素,也就是当前二叉树根节点,之后依次输出二叉树的左孩子和右孩子
    while(stack.length > 0) {
        let cur = stack.pop()
        res.push(cur.val)
        // 先入栈的元素后输出,所以先入栈当前节点右孩子,再入栈左孩子
        cur.right && stack.push(cur.right)
        cur.left && stack.push(cur.left)
    }
    return res
};

中序遍历(inorderTraversal)

第一种方法

const inorderTraversal = function(root) {
    const res = [], stack = []
    while(root || stack.length) {
        // 中序遍历,首先迭代左孩子,左孩子依次入栈
        if(root.left) {
            stack.push(root)
            root = root.left
        // 如果左孩子为空了,输出节点,去右孩子中迭代,
        } else if(root.right) {
            res.push(root.val)
            root = root.right
        // 如果左右孩子都为空了,输出当前节点,栈顶元素出栈,也就是回退到上一层,此时置空节点左孩子,防止while循环重复进入
        } else if(!root.left && !root.right) {
            res.push(root.val)
            root = stack.pop()
            root && (root.left = null)
        }
    }
    return res
};

第二种方法(第一种优化)

我们在上一种方法里,条件判断root.left,root.right,其实我们可以只考虑当前节点node,这样我们只需要判断node是否存在,简化代码

 const inorderTraversal = function(root) {
    const res = [], stack = []
    let node = root;
    while (stack.length > 0 || node !== null) {
        // 这里用当前节点node是否存在,简化代码,
        if (node) {
            stack.push(node);
            node = node.left
        } else {
            node = stack.pop();
            res.push(node.val);
            node = node.right;
        }
    }
    return res;
};

后序遍历(postorderTraversal)

第一种方法

// 1, 先依次遍历左孩子, 在栈中依次记录,当左孩子为空时,遍历到叶子节点 //跳回上一层节点, 为防止while循环重复进入,将上一层左孩子置为空
// 2, 接着遍历右孩子, 在栈中依次记录值,当右孩子为空时, 遍历到叶子节点
// 跳回上一层节点, 为防止while循环重复进入,将上一层右孩子置为空
const postorderTraversal = function(root) {
    let res = [], stack = []
    while (root || stack.length) {
        if (root.left) {
            stack.push(root)
            root = root.left
        } else if (root.right) {
            stack.push(root)
            root = root.right
        } else {
            res.push(root.val)
            root = stack.pop()
            if (root && root.left) root.left = null
            else if (root && root.right) root.right = null
        }
    }
    return res
};

第二种方法(逆序思维)

再回头看看前序遍历的代码,实际上后序遍历和前序遍历是一个逆序过程

// 结果数组中依次进入的是节点的左孩子,右孩子,节点本身,注意使用的是
// unshift,与前序遍历push不同,每次数组头部添加元素,实际上就是前序 遍历的逆序过程
const postorderTraversal = function(root) {
    const res = [], stack = []
    while (root || stack.length) {
        res.unshift(root.val)
        root.left && stack.push(root.left)
        root.right && stack.push(root.right)
        root = stack.pop()
    }
    return res
};

第三种方法(逆序思维的另一种写法)

// 和前序遍历区别在于,结果数组res中入栈顺序是当前节点,右孩子,左孩子,最后
// 使用js数组reverse方法反转(逆序),使得输出顺序变为左孩子,右孩子,当前节点,实现后序遍历
const postorderTraversal = function(root) {
    let stack = [], res = []
    root && stack.push(root)
    while(stack.length > 0) {
        let cur = stack.pop()
        res.push(cur.val)
        cur.left && stack.push(cur.left)
        cur.right && stack.push(cur.right)
    }
    return res.reverse()
};

本文详细介绍了二叉树前中后序遍历的非递归实现,核心是借助一个栈stack,使用迭代的方式模拟递归过程