[数据结构与算法]NC136 输出二叉树的右视图

什么是右视图

法一

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 求二叉树的右视图
 * @param xianxu int整型一维数组 先序遍历
 * @param zhongxu int整型一维数组 中序遍历
 * @return int整型一维数组
 */
function TreeNode(val){
    this.val = val;
    this.left = null;
    this.right = null;
}

function findIndex(target, zhongxu){
    for(let i = 0; i < zhongxu.length; i++){
        if(target == zhongxu[i]){
            return i;
        }
    }
    return 0;
}
// build binary tree
function build(xianxu, zhongxu){
    if(!xianxu || !zhongxu || !xianxu.length || !zhongxu.length){
        return null;
    }
    let root = new TreeNode(xianxu[0]);
    let index = findIndex(xianxu[0], zhongxu);
    root.left = build(xianxu.slice(1, index + 1), zhongxu.slice(0, index));
    root.right = build(xianxu.slice(index + 1, xianxu.length), zhongxu.slice(index + 1, zhongxu.length));
    return root;
}

// save result
let res = [];

// right view of binary tree
// The tree's hierarchical traversal outputs the last element of each layer
function rightView(root){
    let queue = [];
    queue.push(root);
    while(queue.length != 0){
        let size = queue.length;
        for(let i = 0; i < size; i++){
            let first = queue.shift();
            first.left && queue.push(first.left);
            first.right && queue.push(first.right);
            if(i == size - 1){
                res.push(first.val);
            }
        }
    }
}
function solve( xianxu ,  zhongxu ) {
    if(xianxu.length == 0 || zhongxu.length == 0){
        return res;
    }
    let buildedTree = build(xianxu, zhongxu);
    rightView(buildedTree);
    return res;
}
module.exports = {
    solve : solve
};

法二

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 求二叉树的右视图
 * @param xianxu int整型一维数组 先序遍历
 * @param zhongxu int整型一维数组 中序遍历
 * @return int整型一维数组
 */
function TreeNode(val){
    this.val = val;
    this.left = null;
    this.right = null;
}

function findIndex(target, zhongxu){
    for(let i = 0; i < zhongxu.length; i++){
        if(target == zhongxu[i]){
            return i;
        }
    }
    return 0;
}
// build binary tree
function build(xianxu, zhongxu){
    if(!xianxu || !zhongxu || !xianxu.length || !zhongxu.length){
        return null;
    }
    let root = new TreeNode(xianxu[0]);
    let index = findIndex(xianxu[0], zhongxu);
    root.left = build(xianxu.slice(1, index + 1), zhongxu.slice(0, index));
    root.right = build(xianxu.slice(index + 1, xianxu.length), zhongxu.slice(index + 1, zhongxu.length));
    return root;
}

// save result
let res = [];
let maxDep = 0;

// right view of binary tree
// Recursive method for right view
function rightView(root, curDep){
    if(!root) return null;
    if(curDep > maxDep){
        maxDep = curDep;
        res.push(root.val);
    }
    root.right && rightView(root.right, curDep + 1);
    root.left && rightView(root.left, curDep + 1);
    return;
}
function solve( xianxu ,  zhongxu ) {
    if(xianxu.length == 0 || zhongxu.length == 0){
        return res;
    }
    let buildedTree = build(xianxu, zhongxu);
    rightView(buildedTree, 1);
    return res;
}
module.exports = {
    solve : solve
};