993 Cousins in Binary Tree 二叉樹的堂兄弟節(jié)點

Description:
In a binary tree, the root node is at depth 0, and children of each depth k node are at depth k+1.

Two nodes of a binary tree are cousins if they have the same depth, but have different parents.

We are given the root of a binary tree with unique values, and the values x and y of two different nodes in the tree.

Return true if and only if the nodes corresponding to the values x and y are cousins.

Example:

Example 1:

Binary Tree 1

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

Example 2:

Binary Tree 2

Input: root = [1,2,3,null,4,null,5], x = 5, y = 4
Output: true

Example 3:

Binary Tree 3

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

Note:

The number of nodes in the tree will be between 2 and 100.
Each node has a unique integer value from 1 to 100.

題目描述:
在二叉樹中，根節(jié)點位于深度 0 處，每個深度為 k 的節(jié)點的子節(jié)點位于深度 k+1 處。

如果二叉樹的兩個節(jié)點深度相同，但父節(jié)點不同，則它們是一對堂兄弟節(jié)點。

我們給出了具有唯一值的二叉樹的根節(jié)點 root，以及樹中兩個不同節(jié)點的值 x 和 y。

只有與值 x 和 y 對應(yīng)的節(jié)點是堂兄弟節(jié)點時，才返回 true。否則，返回 false。

示例 :

示例 1：

二叉樹1

輸入：root = [1,2,3,4], x = 4, y = 3
輸出：false

示例 2：

二叉樹2

輸入：root = [1,2,3,null,4,null,5], x = 5, y = 4
輸出：true

示例 3：

二叉樹3

輸入：root = [1,2,3,null,4], x = 2, y = 3
輸出：false

提示：

二叉樹的節(jié)點數(shù)介于 2 到 100 之間。
每個節(jié)點的值都是唯一的、范圍為 1 到 100 的整數(shù)。

思路:

1. 層序遍歷, 如果x, y在同一層, 且不是相鄰的兩個結(jié)點(較小的結(jié)點的下標(biāo)不能為偶數(shù)), 則為堂兄弟結(jié)點, 如果為空, 可以在該層加入 0或者 null
2. 遍歷同時記錄下結(jié)點的高度和父結(jié)點, 比較 x和 y的高度和父結(jié)點即可
   時間復(fù)雜度O(n), 空間復(fù)雜度O(n)

代碼:
C++:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution 
{
public:
    bool isCousins(TreeNode* root, int x, int y) 
    {
        dfs(root, x, y, 0);
        return (height_x == height_y) && (parent_x != parent_y);
    }
private:
    int height_x = -1, height_y = -1, parent_x = -1, parent_y = -1;
    void dfs(const TreeNode* root, const int x, const int y, const int h)
    {
        if (!root) return;
        if (root -> left and root -> left -> val == x or root -> right and root -> right -> val == x)
        {
            parent_x = root -> val;
            height_x = h;
        }
        if (root -> left and root -> left -> val == y or root -> right and root -> right -> val == y)
        {
            parent_y = root -> val;
            height_y = h;
        }
        dfs(root -> left, x, y, h + 1);
        dfs(root -> right, x, y, h + 1);
    }
};

Java:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private Map<Integer, Integer> depth;
    private Map<Integer, TreeNode> parent;

    public boolean isCousins(TreeNode root, int x, int y) {
        depth = new HashMap();
        parent = new HashMap();
        dfs(root, null);
        return (depth.get(x) == depth.get(y) && parent.get(x) != parent.get(y));
    }

    public void dfs(TreeNode node, TreeNode par) {
        if (node != null) {
            depth.put(node.val, par != null ? 1 + depth.get(par.val) : 0);
            parent.put(node.val, par);
            dfs(node.left, node);
            dfs(node.right, node);
        }
    }
}

Python:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
        queue = [root]
        while queue:
            size, level = len(queue), []
            for _ in range(size):
                cur = queue.pop(0)
                if cur:
                    level.append(cur.val)
                    queue.append(cur.left)
                    queue.append(cur.right)
                else:
                    level.append(0)
            if x in level and y in level:
                index_x, index_y = min(level.index(x), level.index(y)), max(level.index(x), level.index(y))
                if index_x + 1 == index_y and not (index_x & 1):
                    return False
                return True
            if x in level or y in level:
                return False
        return False