Найдите, являются ли два узла кузенами или узлами-родителями в двоичном дереве в JavaScript

Question

Я знаю, что идея состоит в том, чтобы сначала выполнить обход порядка на дереве.

Если узлы находятся на одном уровне и их родители не совпадают, они равны двоюродные братья .

А если совпадения, то они братья и сестры .

Я могу сделать прохождение порядка уровней по

BinarySearchTree.prototype.levelOrderTraversal = function() {
    var q = [];
    var results = [];
    var _root = this.root;
    if(_root) {
        q.push(_root);
        while(q.length > 0) {
            var temp = q.shift();
            results.push(temp.value);
            if(temp.left) {
                q.push(temp.left);
            }
            if(temp.right) {
                q.push(temp.right);
            }
        }
        return results;
    }else {
        return null;
    }

}

Но теперь как это сделатьЯ слежу за родителями, чтобы я мог найти, что данные узлы - это братья и сестры или родственники?

Например,

, если мой обход порядка уровней дает мне

[3, 2,4, 1, 5]

3 - корень, 2 и 4 - братья и сестры или родитель 3.

1 - левый потомок родителя 2.

5 является правым потомком родителя 4.

так, 1 и 5 - узлы двоюродного брата, в то время как 2 и 4 - узлы родного брата.

Answer 1

Вы можете сохранить путь к нужным узлам и проверить одинаковую длину путей и последнего или элемента перед последним для получения отношения.

function getPath(node, value, path = []) {
    if (!node) {
        return;
    }
    if (node.value === value) {
        return path;
    }
    return getPath(node.left, value, path.concat(node.value))
        || getPath(node.right, value, path.concat(node.value));
}

function findRelation(root, a, b) {
    var pathA = getPath(root, a),
        pathB = getPath(root, b);

    if (pathA.length !== pathB.length) {
        return;
    }
    if (pathA.length && pathA[pathA.length - 1] === pathB[pathB.length - 1]) {
        return 'siblings';
    }

    if (pathA.length > 1 && pathA[pathA.length - 2] === pathB[pathB.length - 2]) {
        return 'cousins';
    }
}

var tree = { value: 3, left: { value: 2, left: { value: 1 } }, right: { value: 4, right: { value: 5 } } };

console.log(findRelation(tree, 2, 4));
console.log(findRelation(tree, 1, 5));