javascript - BinTree 类型脚本上的 Inorder

Question

我的任务是实现一个函数，该函数迭代 bin 树并按顺序返回其所有值的数组。代码如下:

interface BinTree {
root: number;
left?: BinTree;
right?: BinTree;
 };
 const TreeInArray =(t:BinTree):number[] =>{
       let list = new Array<number>(); 
        if (t.left!=undefined) { 
            list = list.concat(TreePreArray(t.left))  
        }
       list.push(t.root)
       if (t.right!=undefined) { 
          list = list.concat(TreePreArray(t.right))
        }
    return list
 }
 let bn1 : BinTree = { // DOES NOT PASS TYPE CHECKING
 root: 1,
 left: { root: 2 ,
    left:{root:4 },right:{root:5 } },
 right: { root: 3}
 }
 console.log((TreeInArray(bn1)));

输出为

[ 2, 4, 5, 1, 3 ]

我期望输出与此类似

[4, 2, 5, 1, 3]

这是什么原因？

Answer 1

您正在递归调用预购版本而不是有序版本:

const TreeInArray = (t: BinTree): number[] => {
    let list = new Array<number>();
    if (t.left != undefined) {
        list = list.concat(TreeInArray(t.left))
    }
    list.push(t.root)
    if (t.right != undefined) {
        list = list.concat(TreeInArray(t.right))
    }
    return list
}