leetcode-993.png

找堂兄弟节点
层次一样深，但是父节点不是同一个

找到等于 x、y的节点，并且记录下来深度Depth以及他们的父节点

DFS

var isCousins = function (root, x, y) {
    let xParent = null, yParent = null
    let xDepth = 0, yDepth = 0
    var dfs = function (root, parent, depth) {
        if (!root) return
        if (root.val === x) {
            xParent = parent
            xDepth = depth
        }
        if (root.val === y) {
            yParent = parent
            yDepth = depth
        }
        dfs(root.left, root, depth + 1)
        dfs(root.right, root, depth + 1)
    }
    dfs(root, null, 0)
    return xParent !== yParent && xDepth === yDepth
};

BFS

var isCousins = function (root, x, y) {
    let queue = []
    queue.push(root)
    while (queue.length) {
        let xParent = null, yParent = null
        let size = queue.length
        for (let i = 0; i < size; ++i) {
            let node = queue.shift()
            if (node.left) {
                queue.push(node.left)
                if (node.left.val === x) {
                    xParent = node
                } else if (node.left.val === y) {
                    yParent = node
                }
            }
            if (node.right) {
                queue.push(node.right)
                if (node.right.val === x) {
                    xParent = node
                } else if (node.right.val === y) {
                    yParent = node
                }
            }
        }
        if (xParent && yParent) {
            return xParent !== yParent
        }
    }
    return false
};