打印二叉树的边界节点.js

给定一颗二叉树的头结点，按照下面的规则实现二叉树的边界节点的逆时针打印。

• 头结点的边界节点
• 叶子节点为边界节点
• 如果节点在所在层的最左边或者最右边，那么也是边界节点

比如这棵树

var getHeight = function(h,l){
    if(h === undefined){
        return l;
    }
    return Math.max(getHeight(h.left, l+1), getHeight(h.right, l+1));
};

var setEdgeMap = function(h, l, edgeMap){
    if(h === undefined){
        return ;
    }
    // 左节点
    // 这里有判断是因为到了右子树循环时，不被覆盖
    edgeMap[l][0] = edgeMap[l][0] === undefined ? h: edgeMap[l][0];
    // 右节点
    edgeMap[l][1] = h;
    setEdgeMap(h.left, l+1, edgeMap);
    setEdgeMap(h.right, l+1, edgeMap);
};

var printLeafNotInMap = function(h, l, m){
    if(h === undefined){
        return ;
    }
    if(h.left === undefined && h.right === undefined && h !== m[l][0] && h !== m[l][1]){
        console.log(h.val+ ' ');
    }
    printLeafNotInMap(h.left, l+1, m);
    printLeafNotInMap(h.right, l+1, m);
};

var printEdge = function(head){
    if(head === undefined){
        return;
    }
    const height = getHeight(head, 0);
    let edgeMap = [];
    for(let i=0; i<height; i++){
        edgeMap.push([]);
    }
    setEdgeMap(head, 0, edgeMap);
    for(let i=0; i !==edgeMap.length; i++){
        console.log(edgeMap[i][0].val + " ");
    }
    printLeafNotInMap(head, 0, edgeMap);
    for(let i= edgeMap.length-1; i !== -1; i--){
        console.log(edgeMap[i][1].val + " ");
    }
}

var tree = {
    val:1,
    left:{
        val:2,
        right:{
            val:4,
            left:{
                val:7,
            },
            right:{
                val:8,
                right:{
                    val:11,
                    left:{
                        val:13,
                    },
                    right:{
                        val:14
                    }
                }
            }
        }
    },
    right:{
        val:3,
        left:{
            val:5,
            left:{
                val:9,
                left:{
                    val:12,
                    left:{
                        val:15,
                    },
                    right:{
                        val:16
                    }
                }
            },
            right:{
                val:10
            }
        },
        right:{
            val:6,
        }
    }
};

printEdge(tree);