es 实现二叉树的前序中序，后序遍历，后序中序还原二叉树，前序中序还原二叉树，二叉树的比较diff

// 二叉树
class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
    /**
     * 二叉树的前序遍历
     * @returns {null}
     * @constructor
     */
    DLR() {
        if (!this) return null;
        // 输出当前的
        console.log(this.value);
        this.left && this.left.DLR();
        this.right && this.right.DLR();
    }
    /**
     * 二叉树的中序遍历
     * @returns {null}
     * @constructor
     */
    LDR() {
        if (!this) return null;
        // 先遍历左边
        this.left && this.left.LDR();
        // 遍历自己
        console.log(this.value);
        // 遍历右边
        this.right && this.right.LDR();
    }
    /**
     * 后序遍历
     * @returns {null}
     * @constructor
     */
    LRD() {
        if (!this) return null;
        // 先遍历左边
        this.left && this.left.LRD();
        // 遍历右边
        this.right && this.right.LRD();
        // 遍历自己
        console.log(this.value);
    }
    /**
     * 获取一颗二叉树的深度
     * @returns {number}
     */
    getDepth() {
        if (!this) return 0;
        return 1 + Math.max(this.left && this.left.getDepth(), this.right && this.right.getDepth())
    }
    /**
     * 二叉树的深度优先搜索 其实就是二叉树的前序遍历
     * @param target {String} 目标的值
     * @returns {boolean} 结果
     */
    searchByDepth(target = '') {
        if (!this || !target) return false;
        if (this.value === target) return true;
        return !!(this.left && this.left.searchByDepth(target)) || !!(this.right && this.right.searchByDepth(target))
    }
    /**
     * 二叉树的深度优先搜索
     * @param target {String} 搜索的值
     * @returns {boolean} 结果
     */
    searchByWidth(target = "") {
        if (!this || !target) return false;
        let _searchByWidth = (nodeArr = []) => {
            if (nodeArr.length < 1) return false;
            let nextLayer = [];
            for (let i = 0, l = nodeArr.length; i < l; i++) {
                if (nodeArr[i].value === target) return true;
                else {
                    nodeArr[i].left && nextLayer.push(nodeArr[i].left)
                    nodeArr[i].right && nextLayer.push(nodeArr[i].right)
                }
            }
            return _searchByWidth(nextLayer);
        }
        return _searchByWidth([this]);
    }
}
// 前序遍历的结果 A B D E C
// 中序遍历的结果 D B E A C
// 后序遍历的结果 D E B C A
/**
 * 通过前序和中序还原二叉树
 * @param qArr {Array} 前序列表
 * @param zArr {Array} 后序列表
 * @returns {Node|null} 二叉树节点
 */
function getNodeByQZ(qArr, zArr) {
    if (qArr.length !== zArr.length || qArr.length === 0) return null;
    let rootVal = qArr[0], root = new Node(rootVal), rootIndex = zArr.indexOf(rootVal);
    let zLeft = zArr.slice(0, rootIndex), qLeft = qArr.slice(1, rootIndex + 1);
    let zRight = zArr.slice(rootIndex + 1), qRight = qArr.slice(rootIndex + 1);
    root.left = getNodeByQZ(qLeft, zLeft);
    root.right = getNodeByQZ(qRight, zRight);
    return root;
}
// 中序遍历的结果 D B E A C
// 后序遍历的结果 D E B C A
/**
 * 通过中序和后序还原二叉树
 * @param zArr {Array} 中序数组
 * @param hArr {Array} 后序数据
 * @returns {Node|null} 合并的二叉树
 */
function getNodeByZH(zArr, hArr) {
    if (zArr.length !== hArr.length || zArr.length === 0) return null;
    let rootIndex = zArr.indexOf(hArr[hArr.length - 1]), root = new Node(hArr[hArr.length - 1]);
    let zLeft = zArr.slice(0, rootIndex), hLeft = hArr.slice(0, rootIndex);
    let zRight = zArr.slice(rootIndex + 1), hRight = hArr.slice(rootIndex, hArr.length - 1);
    root.left = getNodeByZH(zLeft, hLeft);
    root.right = getNodeByZH(zRight, hRight);
    return root;
}
// 比较两颗二叉树的异同
/**
 * 两颗二叉树的比较异同
 * @param root1 {Node}
 * @param root2 {Node}
 * @returns {[]|*[]}
 */
function diff(root1, root2) {
    let result = []
    if (!root1 && !root2) return [];
    else if (root1 && !root2) result.push({type: '删除', from: root1, to: root2});
    else if (!root1 && root2) result.push({type: '新增', from: root1, to: root2});
    else if (root1.value === root2.value) {
        let leftResult = diff(root1.left, root2.left)
        let rightResult = diff(root1.right, root2.right)
        result = [...result, ...leftResult, ...rightResult];
    } else {
        result.push({type: '更新', from: root1, to: root2})
        let leftResult = diff(root1.left, root2.left)
        let rightResult = diff(root1.right, root2.right)
        result = [...result, ...leftResult, ...rightResult];
    }
    return result;
}

// 创建一个二叉树
let a = new Node('A');
let b = new Node('B');
let c = new Node('C');
let d = new Node('D');
let e = new Node('E');
a.left = b;
a.right = c;
b.left = d;
b.right = e;
// a.DLR();  // 前序遍历的结果 A B D E C
// a.LDR();  // 中序遍历的结果 D B E A C
// a.LRD();  // 后序遍历的结果 D E B C A
// console.log(a.getDepth()); // 获取的深度 3
// console.log(a.searchByDepth('E')); // true
// console.log(a.searchByDepth('F')); // false
// console.log(a.searchByWidth('E')); // true
// console.log(a.searchByWidth('F')); // false
// console.log(getNodeByQZ(['A', 'B', 'D', 'E', 'C'], ['D', 'B', 'E', 'A', 'C']));
// console.log(getNodeByZH(['D', 'B', 'E', 'A', 'C'], ['D', 'E', 'B', 'C', 'A']));

let root1 = getNodeByQZ(['A', 'B', 'D', 'E', 'C'], ['D', 'B', 'E', 'A', 'C']);
let root2 = getNodeByQZ(['A', 'B', 'D', 'C', 'F'], ['D', 'B', 'A', 'F', 'C']);
console.log(diff(root1, root2));