二叉树先中后遍历

先序遍历

const bt = require('./bt')
/**
 * 先序遍历算法口诀
 * 1.访问 根 节点
 * 2.对根节点的 左 子树进行先序遍历
 * 3.对根节点的 右 子树进行先序遍历
 */

/**
 * 先序遍历
 * 根 - 左 - 右
 * @param {*} root 
 * @returns 
 */
function preorder(root) {
    if (!root) return
    // 1.访问 根 节点
    console.log(root.val)

    // 2.对根节点的 左 子树进行先序遍历
    preorder(root.left)

    // 3.对根节点的 右 子树进行先序遍历
    preorder(root.right)
}


/*
        1
     /   \
    2     3
   / \    / \
  4   5  6   7
*/
// preorder(bt) // 1,2,4,5,3,6,7

// 非递归版本
function preorder(root) {
    if (!root) return

    const stack = [root]

    /**
     * 出栈就是输出
     * 
     * 第一次入栈，stack: [1]
     * 出栈1，statck: []
     * 入栈右左 ，stack: [3,2]
     * 出栈2：stack: [3]
     * 入栈右左：stack[3,5,4]
     * 出栈4：stack: [3,5]
     * 出栈5: stack: [3]
     * 出栈3： stack: []
     * 入栈右左：stack: [7,6]
     * 出栈6: stack: [7]
     * 出栈7: stack: []
     */
    while (stack.length) {
        const node = stack.pop()
        // 1.访问 根 节点
        console.log(node.val)

        // 3.对根节点的 右 子树进行先序遍历
        if (node.right) {
            stack.push(node.right)
        }

        // 栈 - 后进先出
        // 2.对根节点的 左 子树进行先序遍历
        if (node.left) {
            stack.push(node.left)
        }
        // 循环一次得到的栈：stack: [right, left]
    }
}

preorder(bt) // 1,2,4,5,3,6,7

中序遍历

/**
 * 中序遍历算法口诀
 * 1.对根节点的左子树进行中序遍历
 * 2.访问根节点
 * 3.对根节点的右子树进行中序遍历
 */

const bt = require('./bt')

/**
 * 中序遍历
 * 左-根-右
 * 
 * @param {*} root 
 * @returns 
 */
function inorder(root) {
    if (!root) return

    // 1.对根节点的左子树进行中序遍历
    inorder(root.left)

    // 2.访问根节点
    console.log(root.val)

    // 3.对根节点的右子树进行中序遍历
    inorder(root.right)
}

/*
       1
     /   \
    2     3
   / \   / \
  4  5  6   7
*/
// inorder(bt) // 4,2,5,1,6,3,7

function inorder(root) {
    if (!root) return

    const stack = []
    let p = root;

    /**
     * 入栈1：stack: [1]
     * 入栈1左节点2: stack: [1,2] p =2
     * 入栈2左节点4: stack: [1,2,4]
     *  4下无right节点，p = null,第二个while循环结束，
     * 出栈4：stack: [1,2], 
     * 出栈2，stack: [1], 2下存在right节点，p = 5
     * 入栈5，stack: [1,5], 5下无right节点,p=null
     * 出栈5, stack: [1]
     * 出栈1，stack: [], p = 3
     * 入栈3，stack: [3]
     * 入栈6，stack: [3,6]
     * 出栈6，stack: [3], 6下无节点
     * 出栈3，stack: [3], 3下有节点：p = 7
     * 出栈7
     */


    while (stack.length || p) {
        // 这个 while 的作用是把寻找最左叶子结点的过程中，途径的所有结点都记录下来 
        while (p) {
            stack.push(p)
            // 1.对根节点的左子树进行中序遍历
            p = p.left
        }

        const node = stack.pop()
        // 2.访问根节点
        console.log(node.val)
        // 3.对根节点的右子树进行中序遍历
        p = node.right
    }
}

inorder(bt) // 4,2,5,1,6,3,7

后序遍历

/**
 * 后序遍历算法口诀
 * 1.对根节点的左子树进行后序遍历
 * 2.对根节点的右子树进行后序遍历
 * 3.访问根节点
 */
const bt = require('./bt')

/**
 * 后序遍历
 * 左-右-根
 * 
 * @param {*} root 
 * @returns 
 */
function postorder(root) {
    if (!root) return

    // 1.对根节点的左子树进行后序遍历
    postorder(root.left)

    // 2.对根节点的右子树进行后序遍历
    postorder(root.right)

    // 3.访问根节点
    console.log(root.val)
}


/*
       1
     /   \
    2     3
   / \   / \
  4  5  6   7
*/
// postorder(bt) // 4,5,2,6,7,3,1

// 非递归版本
function postorder(root) {
    if (!root) return

    const stack = [root]
    const outputStack = []

    /**
     * 入栈：stack: [1]
     * 出栈1，stack: []
     * 入栈1左右节点：stack: [2,3]
     * 出栈3：stack: [2]
     * 入栈3左右节点：stack: [2,6,7]
     * 出栈7: stack: [2,6]
     * 出栈6: stack: [2]
     * 出栈2: stack: []
     * 入栈2的左右节点：stack: [4,5]
     * 出栈5: stack: [4]
     * 出栈4: stack: []
     * 
     * 出栈即是 outputStack 入栈
     * 最后 outputStack 分别出栈输出
     */

    while (stack.length) {
        const node = stack.pop()
        outputStack.push(node)

        // 1.对根节点的左子树进行后序遍历
        if (node.left) {
            stack.push(node.left)
        }
        // 2.对根节点的右子树进行后序遍历
        if (node.right) {
            stack.push(node.right)
        }
    }

    while (outputStack.length) {
        // 3.访问根节点
        const node = outputStack.pop()
        console.log(node.val)
    }
}

postorder(bt) // 4,5,2,6,7,3,1