二叉树的先中后序遍历

[Jason-linjiayu]

先放颗二叉树

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

[Jason-linjiayu]

先序遍历

根左右

递归版

const preOrder =(root)=> {
    if(!root) return
    console.log(root.val)
    if(root.left) preOrder(root.left)
    if(root.right) preOrder(root.right)
}
preOrder(tree) // 1245367

非递归版

const preOrder = (root) => {
    if(!root) return
    const stack = [root]
    while(stack.length) {
        const n = stack.pop();
        console.log(n.val)
        if(n.right) stack.push(n.right)
        if(n.left) stack.push(n.left)
    }
}
preOrder(tree) //1245367

[Jason-linjiayu]

中序遍历

左根右

递归版

const inOrder = (root) => {
    if(!root) return
    if(root.left) inOrder(root.left)
    console.log(root.val)
    if(root.right) inOrder(root.right)
}
inOrder(tree)  // 4251637

非递归版

const inOrder = (root) => {
    if(!root) return
    const stack = []
    let p = root
    while(stack.length || p) {
        while(p) {
            stack.push(p)
            p = p.left
        }
        const n = stack.pop()
        console.log(n.val)
        p = n.right
    }
}
inOrder(tree)  // 4251637

[Jason-linjiayu]

后序遍历

左右根

递归版

const postOrder = (root) => {
    if(!root) return
    if(root.left) postOrder(root.left)
    if(root.right) postOrder(root.right)
    console.log(root.val)
}
postOrder(tree) // 4526731

非递归版

const postOrder = (root) => {
    if(!root) return
    const stack = [root]

    const outputStack = []
    while(stack.length) {
        const n = stack.pop()
        outputStack.push(n)
        if(n.left ) stack.push(n.left)
        if(n.right) stack.push(n.right)
    }
    while(outputStack.length) {
        const p = outputStack.pop()
        console.log(p.val)
    }
}
postOrder(tree)

[Jason-linjiayu]

已知中后序遍历求前序遍历，inOrder = [9,3,15,20,7],postOrder = [9,15,7,20,3]。

思路，先把二叉树还原，再求先序；顺便拿下LeetCode 106题

const inOrder = [9,3,15,20,7]
const postOrder = [9,15,7,20,3]

const getTree = (inOrder, postOrder) => {
    if(!inOrder.length || !postOrder.length) return null
    const root = postOrder[postOrder.length - 1];
    const rootIndex = inOrder.indexOf(root)
    const leftInOrder = inOrder.slice(0,rootIndex)
    const rightInOrder = inOrder.slice(rootIndex+1)
    const leftPostOrder = postOrder.slice(0,rootIndex)
    const rightPostOrder = postOrder.slice(rootIndex, postOrder.length-1)
    return {
        val: root,
        left: getTree(leftInOrder,leftPostOrder),
        right: getTree(rightInOrder, rightPostOrder)
    }
}
const tree = getTree(inOrder,postOrder)

const dfs = (root) => {
    if(!root) return;
    console.log(root.val)
    if(root.left)dfs(root.left)
    if(root.right) dfs(root.right)
}
dfs(tree)