二叉树遍历

[Lirx-Xin]

二叉树

二叉树就是指每个节点只能有两个子节点的树，一个是左侧子节点，一个是右侧子节点。

二叉搜索树(BST) 也是一种二叉树，只不过它有一个特性，就是它的每个节点存储的值都要大于左子节点存储的值，小于右子树节点存储的值。

遍历二叉树

前序遍历

/** 递归遍历 */
function preorderTraversal(root,arr = []){
    if(root){
        arr.push(root.val)
        preorderTraversal(root.left,arr)
        preorderTraversal(root.right,arr)
    }
    return arr
}
/** 非递归遍历 */
function preorderTraversal(root){
    let result = []
    let stack = []
    let current = root
    while(current || stack.length){
        while(current){ //先push进根节点与所有左子树节点
            result.push(current.val)
            stack.push(current)
            current = current.left
        }
        current = stack.pop() //从下向上取出已遍历的左节点
        current = current.right //找出已遍历的左子树的右节点，并对其进行先序遍历
    }
}

中序遍历

/** 递归遍历 */
function preorderTraversal(root,arr = []){
    if(root){
        preorderTraversal(root.left,arr)
        arr.push(root.val)
        preorderTraversal(root.right,arr)
    }
    return arr
}
/** 非递归遍历 */
function preorderTraversal(root){
    let result = []
    let stack = []
    let current = []
    while(current || stack.length){
        while(current){
            stack.push(current)
            current = current.left
        }
        current = stack.pop()
        result.push(current.val)
        current = current.right
    }
    return result
}

后序遍历

/** 递归遍历 */
function preorderTraversal(root,arr = []){
    if(root){
        preorderTraversal(root.left,arr)
        preorderTraversal(root.right,arr)
        arr.push(root.val)
    }
    return arr
}
/** 非递归遍历 */
function preorderTraversal(root){
    let result = []
    let stack = []
    let cache = null
    let current = []
    while(current || stack.length){
        while(current){
            stack.push(current)
            current = current.left
        }
        current = stack[stack.length-1]
        if(!current.right || current.right == cache){
            current = stack.pop()
            result.push(current.val)
            cache = current
            current = null
        }else{
            current = current.right
        }
    }
    return result
}

重建二叉树

给定一个二叉树的前序遍历和中序遍历，返回该二叉树。

function stackToTree(pre,vin){
    if(pre.length === 0){
        return null
    }
    if(pre.length === 1){
        return new treeNode(pre[0])
    }
    var root = pre[0]
    var vinrootidx = vin.indexOf(root)
    var vinleft = vin.slice(0,vinrootidx)
    var vinright = vin.slice(vinrootidx+1)
    var preleft = pre.slice(1,vinrootidx+1)
    var preright = pre.slice(vinrootidx+1)
    const node = new treeNode(root)
    node.left = stackToTree(preleft,vinleft)
    node.right = stackToTree(preright,vinright)
    return node
}