算法

二叉树的比较

updated on 

function Node(value) {
    this.value = value;
    this.left = null;
    this.right = null;
}

let a1 = new Node('a');
let b1 = new Node('b');
let c1 = new Node('c');
let d1 = new Node('d');
let e1 = new Node('e');
let f1 = new Node('f');
let g1 = new Node('g');

a1.left = c1;
a1.right = b1;
c1.left = f1;
c1.right = g1;
b1.left = d1;
b1.right = e1;

let a2 = new Node('a');
let b2 = new Node('b');
let c2 = new Node('c');
let d2 = new Node('d');
let e2 = new Node('e');
let f2 = new Node('f');
let g2 = new Node('g');


a2.left = c2;
a2.right = b2;
c2.left = f2;
c2.right = g2;
b2.left = d2;
b2.right = e2;

/* 左右两边必须相等 */
function compareTree(root1, root2) {
    if (root1 == root2) { // 是同一颗树
        return true;
    }
    if (root1 == null && root2 != null || root2 == null && root1 != null) {
        return false;
    }
    if (root1.value != root2.value) { // 相同位置的值不相等
        return false;
    }
    let leftBoolen = compareTree(root1.left, root2.left);   // 判断左子树是否相等
    let rightBoolen = compareTree(root1.right, root2.right);    // 判断右子树是否相等
    return leftBoolen && rightBoolen;   // 必须左右子树都相等才算相等
}

console.log(compareTree(a1, a2));

function Node(value) {
    this.value = value;
    this.left = null;
    this.right = null;
}

let a1 = new Node('a');
let b1 = new Node('b');
let c1 = new Node('c');
let d1 = new Node('d');
let e1 = new Node('e');
let f1 = new Node('f');
let g1 = new Node('g');

a1.left = c1;
a1.right = b1;
c1.left = f1;
c1.right = g1;
b1.left = d1;
b1.right = e1;

let a2 = new Node('a');
let b2 = new Node('b');
let c2 = new Node('c');
let d2 = new Node('d');
let e2 = new Node('e');
let f2 = new Node('f');
let g2 = new Node('g');


a2.left = c2;
a2.right = b2;
c2.left = f2;
c2.right = g2;
b2.left = d2;
b2.right = e2;

/* 左右两树可以互换 */
function compareTree(root1, root2) {
    if (root1 == root2) { // 是同一颗树
        return true;
    }
    if (root1 == null && root2 != null || root2 == null && root1 != null) {
        return false;
    }
    if (root1.value != root2.value) { // 相同位置的值不相等
        return false;
    }
    // let leftBoolen = compareTree(root1.left, root2.left);   // 判断左子树是否相等
    // let rightBoolen = compareTree(root1.right, root2.right);    // 判断右子树是否相等
    // return leftBoolen && rightBoolen;   // 必须左右子树都相等才算相等

    return (compareTree(root1.left, root2.left) && compareTree(root1.right, root2.right)) ||
        (compareTree(root1.left, root2.right) && compareTree(root1.right, root2.left))
}

console.log(compareTree(a1, a2));

其他内容