在 JavaScript 的二叉树中查找两个节点是否是表亲节点或兄弟节点

Question

我知道思路是先在树上做层序遍历。

如果在同一级别找到节点并且它们的 parent 不匹配它们是 cousins.

如果匹配，他们是 兄弟姐妹。

我可以通过

进行层序遍历

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;
    }

}

但是现在我如何跟踪 parent 以便我可以找到给定的节点是兄弟姐妹还是堂兄弟姐妹？

例如，

如果我的水平顺序遍历给我

[3、2、4、1、5]

3 是根，2 和 4 是兄弟姐妹或 parent 3.

1 是 parent 2.

的左 child

5 是 parent 4.

的右 child

所以，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));

在 JavaScript 的二叉树中查找两个节点是否是表亲节点或兄弟节点

Find if two nodes are cousin nodes or sibling nodes in Binary Tree in JavaScript

javascript

binary-tree

data-structures