993. Cousins in Binary Tree

leetcode easy

#backtracking#csharp#easy#graph#leetcode#search#tree#two-pointers

Task

Дан корень бинарного дерева с уникальными значениями и значения двух различных узлов дерева x и y. Верните true, если узлы, соответствующие значениям x и y в дереве, являются кузенами, иначе верните false.

Два узла бинарного дерева являются кузенами, если они находятся на одной глубине и имеют разных родителей.

Обратите внимание, что в бинарном дереве корневой узел находится на глубине 0, а дети каждого узла глубины k находятся на глубине k + 1.

Пример

Input: root = [1,2,3,4], x = 4, y = 3

Output: false

C# solution

matched/original

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}
public class Solution {
    private TreeNode parentX = null;
    private TreeNode parentY = null;
    private int depthX = -1;
    private int depthY = -1;
    
    public bool IsCousins(TreeNode root, int x, int y) {
        Dfs(root, null, 0, x, y);
        return depthX == depthY && parentX != parentY;
    }
    
    private void Dfs(TreeNode node, TreeNode parent, int depth, int x, int y) {
        if (node == null) {
            return;
        }
        if (node.val == x) {
            parentX = parent;
            depthX = depth;
        } else if (node.val == y) {
            parentY = parent;
            depthY = depth;
        } else {
            Dfs(node.left, node, depth + 1, x, y);
            Dfs(node.right, node, depth + 1, x, y);
        }
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}
class Solution {
public:
    private TreeNode parentX = null;
    private TreeNode parentY = null;
    private int depthX = -1;
    private int depthY = -1;
    
    public bool IsCousins(TreeNode root, int x, int y) {
        Dfs(root, null, 0, x, y);
        return depthX == depthY && parentX != parentY;
    }
    
    private void Dfs(TreeNode node, TreeNode parent, int depth, int x, int y) {
        if (node == null) {
            return;
        }
        if (node.val == x) {
            parentX = parent;
            depthX = depth;
        } else if (node.val == y) {
            parentY = parent;
            depthY = depth;
        } else {
            Dfs(node.left, node, depth + 1, x, y);
            Dfs(node.right, node, depth + 1, x, y);
        }
    }
}

Java solution

matched/original

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    private TreeNode parentX = null;
    private TreeNode parentY = null;
    private int depthX = -1;
    private int depthY = -1;
    
    public boolean isCousins(TreeNode root, int x, int y) {
        dfs(root, null, 0, x, y);
        return depthX == depthY && parentX != parentY;
    }
    
    private void dfs(TreeNode node, TreeNode parent, int depth, int x, int y) {
        if (node == null) {
            return;
        }
        if (node.val == x) {
            parentX = parent;
            depthX = depth;
        } else if (node.val == y) {
            parentY = parent;
            depthY = depth;
        } else {
            dfs(node.left, node, depth + 1, x, y);
            dfs(node.right, node, depth + 1, x, y);
        }
    }
}

JavaScript solution

matched/original

class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

var isCousins = function(root, x, y) {
    let parentX = null, parentY = null;
    let depthX = -1, depthY = -1;
    
    function dfs(node, parent, depth) {
        if (!node) return;
        if (node.val === x) {
            parentX = parent;
            depthX = depth;
        } else if (node.val === y) {
            parentY = parent;
            depthY = depth;
        } else {
            dfs(node.left, node, depth + 1);
            dfs(node.right, node, depth + 1);
        }
    }
    
    dfs(root, null, 0);
    return depthX === depthY && parentX !== parentY;
};

Go solution

matched/original

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func isCousins(root *TreeNode, x int, y int) bool {
    var parentX, parentY *TreeNode
    var depthX, depthY int = -1, -1

    var dfs func(*TreeNode, *TreeNode, int)
    dfs = func(node *TreeNode, parent *TreeNode, depth int) {
        if node == nil {
            return
        }
        if node.Val == x {
            parentX = parent
            depthX = depth
        } else if node.Val == y {
            parentY = parent
            depthY = depth
        } else {
            dfs(node.Left, node, depth + 1)
            dfs(node.Right, node, depth + 1)
        }
    }

    dfs(root, nil, 0)
    return depthX == depthY && parentX != parentY
}

Explanation

Algorithm

Поиск глубины и родителя для каждого узла:

Используйте поиск в глубину (DFS) для обхода дерева.

Для каждого узла сохраняйте его глубину и родителя, если значение узла равно x или y.

Проверка условий на кузенов:

Узлы являются кузенами, если они находятся на одной глубине, но имеют разных родителей.

Возврат результата:

Если узлы удовлетворяют условиям на кузенов, верните true, иначе верните false.

😎