树的不同形态

[编程题]树的不同形态

热度指数：2956 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定二叉树T（树深度不超过H<=10，深度从1开始，节点个数N<1024，节点编号1~N）的层序和中序遍历，输出T从左向右叶子节点以及树先序和后序遍历序列

输入描述:

输入两行，分别代表层序和中序遍历结果，节点编号按单个空格分开

输出描述:

依次输出  从左向右叶子节点 ，先序， 后序 遍历 。 节点编号按空格分开

示例1

输入

3 5 4 2 6 7 1
2 5 3 6 4 7 1

输出

2 6 1
3 5 2 4 6 7 1
2 5 6 1 7 4 3

算法知识视频讲解

JavaScript

命运石之门

题不是很难，主要难点在于通过层序遍历与中序遍历重建二叉树，树建好了剩下的也就只是小儿科了，应该还能再优化下

function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
}
// 重建二叉树
function reConstructBinaryTree(lev, vin) {
    if (!lev.length || !vin.length) return null;
    const rootVal = lev[0];
    const node = new TreeNode(rootVal);
    let i = 0;
    let levLeft = [];
    let levRight = [];
    for (; i < vin.length; i++) {
        if (vin[i] == rootVal) break;
    }
    for (let k = 0; k < lev.length; k++) {
        for (let j = 0; j < i; j++) {
            if (lev[k] == vin[j]) {
                levLeft.push(lev[k]);
            }
        }
        for (let j = vin.length - 1 ; j > i ; j--) {
            if (lev[k] == vin[j]) {
                levRight.push(lev[k]);
            }
        }
    }
    node.left = reConstructBinaryTree(levLeft, vin.slice(0,i));
    node.right = reConstructBinaryTree(levRight, vin.slice(i + 1));
    return node;
}
// 从左到右节点
let LTR = [];
function ltrTree(tn) {
    if (tn === null) return null;
    ltrTree(tn.left);
    ltrTree(tn.right);
    if (tn.left === null && tn.right === null) {
        LTR.push(tn.val);
    }
}
// 先序遍历
let PRE = [];
function preTree(tn) {
    if (tn === null) return null;
    PRE.push(tn.val);
    preTree(tn.left);
    preTree(tn.right);
}
// 后序遍历
let LRD = [];
function lrdTree(tn) {
    if (tn === null) return;
    lrdTree(tn.left);
    lrdTree(tn.right);
    LRD.push(tn.val);
}
let LEV = readline().split(' ');
let VIN = readline().split(' ');
let tree = reConstructBinaryTree(LEV, VIN);
ltrTree(tree);
preTree(tree);
lrdTree(tree);
print(LTR.join(' '));
print(PRE.join(' '));
print(LRD.join(' '));

发表于 2020-03-03 18:35:34 回复(0)