前言

对于树的结构大家应该不陌生了，对于其前、中、后遍历可以通过递归的方式来实现，那么还可以通过什么来实现呢？

通过栈结构来实现。

正文

树结构

树的结构：

function TreeNode(val) {
    this.val = val;
    this.left = null;
    this.right = null;
}

定义一个下面的树结构来分析其前、中、后序遍历的结、果：

const root = {
    val: 1,
    left:{
        val: 2,
        left: {
            val: 4,
        },
        right: {
            val: 5,
        }
    },
    right:{
        val: 3,
        right: {
            val: 6,
        }
    }
}

前序遍历

结果为：1 2 4 5 3 6

前序遍历的规则：根左右

递归实现

• 先判断该节点是否为空，如果为空就返回
• 输出该节点的值(根节点)
• 采用递归将该节点的左节点传入(左节点)
• 采用递归将该节点的右节点传入(右节点)

function preorder(node) {
        if(!node) {
          return;  
        }
        console.log(node.val);
        preorder(node.left);
        preorder(node.right);
}

栈实现(力扣144题)

var preorderTraversal = function(root) {
const res = [];
const stack = [];
stack.push(root);

while (stack.length) {
    if (!root) return [];
    const cur = stack.pop();
    res.push(cur.val);
    if (cur.right) {
        stack.push(cur.right);
    }
    if (cur.left) {
        stack.push(cur.left);
    }
}

return res;
};

该树的前序遍历通过图来解释如下：

分析：

• 先将root入栈，然后出栈并赋值给cur
• 将cur加入数组res
• 先判断cur的right，如果存在，则压入栈
• 在判断cur的left，如果存在，则压入栈(因为前序遍历为根左右，并且栈为先进后出，所以先判断右节点再判断左节点)
• 一直循环至栈为空
• cur=1时，3和2入栈
• cur=2时，5和4入栈
• cur=4
• cur=5
• cur=3时，6入栈
• cur=6

中序遍历

结果为：4 2 5 1 3 6

中序遍历的规则：左根右

递归实现

• 先判断该节点是否为空，如果为空就返回
• 采用递归将该节点的左节点传入(左节点)
• 输出该节点的值(根节点)
• 采用递归将该节点的右节点传入(右节点)

function inorder(node) {
    if (!node) {
        return;
    }
    inorder(node.left);
    console.log(node.val);
    inorder(node.right);
}

栈实现(力扣94题)

var inorderTraversal = function(root) {
    if (!root) return [];
    const res = [];
    const stack = [];
    let cur = root;

    while (stack.length || cur) {
        while (cur) {
            stack.push(cur);
            cur = cur.left;
        }

        cur = stack.pop();
        res.push(cur.val);
        cur = cur.right;
    }

    return res;
    };

该树的中序遍历通过图来解释如下：

分析：

• 从根节点一直遍历左节点，遍历到的节点入栈，直到该节点不存在左节点时，也就是4，将该节点的值出栈
• 再将顶部元素2出栈，将其右节点赋值给cur
• 一直循环，直到栈为空或者cur为空(因为右节点没有入栈，只有左节点入栈，右节点直接赋值给cur)
• cur=4时，1和2入栈
• cur=2
• cur=5
• cur=1
• cur=3
• cur=6

后序遍历

结果为：4 5 2 6 3 1 后序遍历的规则：左右根

递归实现

• 先判断该节点是否为空，如果为空就返回
• 采用递归将该节点的左节点传入(左节点)
• 采用递归将该节点的右节点传入(右节点)
• 输出该节点的值(根节点)

function postorder(node) {
    if (!node) {
        return;
    }
    postorder(node.left);
    postorder(node.right);
    console.log(node.val);
}

栈实现(力扣145题)

var postorderTraversal = function(root) { 
          if (!root) return [];
        const res = [];
        const stack = [];
        stack.push(root);
        
        
        while (stack.length) {
         
            const cur = stack.pop();
            res.unshift(cur.val);
             if (cur.left) {
                stack.push(cur.left);
            }
            if (cur.right) {
                stack.push(cur.right);
            }
        }
        
        return res;
        };

该树的后序遍历通过图来解释如下：

分析：

• 后序和先序差不多，相当于反着的，所以在后序就是向数组头部加入
• cur=1时，2和3入栈
• cur=3时，6入栈
• cur=6
• cur=2时，4和5入栈
• cur=5
• cur=4

结语