二叉树的创建(先序遍历)

需求

根据一颗二叉树的先序遍历的结果，创建二叉树

[‘a’,’b’,’d’,’#’,’f’,’#’,’#’,’#’,’c’,’#’,’e’,’#’,’#’]; (根左右)

思路

创建根节点

递归地创建左子树

递归地创建右子树

递归的注意事项：

1.递归的结束条件:叶子节点

2.递归的递推表达式(节点之间的关系):根左右

3.递归的返回值:创建好的树或者子树

代码

function TreeNode(val){
    this.val = val;
    this.left = null;
    this.right = null;
}
function createTree_preorder(arr){
    let root = null;
    if(arr[0]!==undefined){
        let rootval = arr.shift();
        if(rootval!=='#'){
            root = new TreeNode(rootval);  //创建根节点
            root.left = createTree_preorder(arr);
            root.right = createTree_preorder(arr);
        }
    }
    return root;
}
let arr = ['a','b','d','#','f','#','#','#','c','#','e','#','#'];
console.log(createTree_preorder(arr));