js刷林扣 lintcode 之二叉树的构造和前中后序遍历

66/67/68. 二叉树的前/中/后序遍历 【03-09】

分别对应的lintcode地址为
二叉树的前序遍历
二叉树的中序遍历
二叉树的后序遍历
之前一直耽搁了好久没刷林扣了，用js写二叉树代码量还是不小，有的地方比较啰嗦，见谅~~

    //构造节点
    function Node(){
        this.text=''
        this.leftChild=null
        this.rightChild=null
    }
    //构造节点数组
    function buildNodes(arr){
        var nodes=[]
        arr.forEach(function(a){
            var node=new Node()
            node.text=a
            nodes.push(node)
        })
        return nodes
    }
    //构造节点树
    function buildNodeTree(arr){
        var nodes=buildNodes(arr)
        var index=0,sharpNum=0 //索引,text为#的节点数
        while(index<nodes.length){
            if(nodes[index].text!='#'){
                nodes[index].leftChild=nodes[2*index+1-sharpNum]
                nodes[index].rightChild=nodes[2*index+2-sharpNum]
            }else{
                sharpNum+=2
            }
            index++
        }
        return nodes
    }

    //遍历
    var res=[]
    //前序遍历
    function firstRoot(node){
        res.push(node.text)
        if(node.leftChild&&node.leftChild.text!='#'){
            firstRoot(node.leftChild)
        }
        else if(node.rightChild&&node.rightChild.text!='#'){
            firstRoot(node.rightChild)
        }else return;
    }
    //中序遍历
    function middleRoot(node){
        if(node.leftChild&&node.leftChild.text!='#'){
            if(node.leftChild.leftChild&&node.leftChild.leftChild.text!='#'){
                middleRoot(node.leftChild)
            }else{res.push(node.leftChild.text)}
        }
        res.push(node.text)
        if(node.rightChild&&node.rightChild.text!='#'){
            if(node.rightChild.leftChild&&node.rightChild.leftChild.text!='#'){
                middleRoot(node.rightChild)
            }else{
                res.push(node.rightChild.text)
            }
        }
        return;
    }
    //后序遍历
    function lastRoot(node){
        if(node.leftChild&&node.leftChild.text!='#'){
            if(node.leftChild.leftChild&&node.leftChild.leftChild.text!='#'){
                middleRoot(node.leftChild)
            }else{res.push(node.leftChild.text)}
        }
        
        if(node.rightChild&&node.rightChild.text!='#'){
            if(node.rightChild.leftChild&&node.rightChild.leftChild.text!='#'){
                middleRoot(node.rightChild)
            }else{
                res.push(node.rightChild.text)
            }
        }
        res.push(node.text)
    }
    //main
    var nodes=buildNodeTree([1,'#',2,3])
    lastRoot(nodes[0])
    console.log(nodes)
    console.log(res.join(',')) //最后结果