二叉树的深度优先遍历

需求

给定一个二叉树，实现先序，中序，后续遍历

思路

先创建一颗二叉树，再进行上述操作

代码

function TreeNode(val) {
    this.val = val;
    this.left = null;
    this.right = null;
}
//给定一个层次遍历产生的数组，生成一颗二叉树
function createTree_levelorder(arr) {
    let rootval = arr.shift();
    let queue = [];
    if (rootval) {
        let root = new TreeNode(rootval); //新建根节点
        queue.push(root); //存入到队列中
        while (queue.length) { //当队列不为空时，出队并进入相关节点
            let node = queue.shift();
            let leftval = arr.shift();
            let rightval = arr.shift();
            if (leftval !== '#') { //左子树不为空
                let left = new TreeNode(leftval); //新建节点
                queue.push(left);
                node.left = left;
            }
            if (rightval !== '#') {
                let right = new TreeNode(rightval);
                queue.push(right);
                node.right = right;
            }

        }
        return root;
    }
}

let arr = ['a', 'b', 'c', 'd', '#', '#', 'e', '#', 'f', '#', '#', '#', '#'];
let root = createTree_levelorder(arr);

function PreOrder(root, arr = []) { //先序遍历
    if (root) {
        arr.push(root.val);
        PreOrder(root.left, arr);
        PreOrder(root.right, arr);
    } else {
        arr.push('#');
    }
}
let res = [];
PreOrder(root, res);
console.log(res);
//'a', 'b', 'd', '#', 'f', '#', '#', '#', 'c', '#', 'e', '#', '#'
function InOrder(root, arr = []) { //中序遍历
    if (root) {
        InOrder(root.left, arr);
        arr.push(root.val);
        InOrder(root.right, arr);
    } else {
        arr.push('#');
    }
}
let res2 = [];
InOrder(root, res2);
console.log(res2);
//'#', 'd', '#', 'f', '#', 'b', '#', 'a', '#', 'c', '#', 'e', '#'
function PostOrder(root, arr = []) {
    if (root) {
        PostOrder(root.left, arr);
        PostOrder(root.right, arr);
        arr.push(root.val);
    } else {
        arr.push('#');
    }
}
let res3 = [];
PostOrder(root, res3);
console.log(res3);
//'#', '#', '#', 'f', 'd', '#', 'b', '#', '#', '#', 'e', 'c', 'a'