LeetCode.993.Cousins in Binary Tree 二叉树中的堂兄弟

题目描述

993 Cousins in Binary Tree
https://leetcode-cn.com/problems/cousins-in-binary-tree/

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 1:

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

Example 2:

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

Example 3:

Input: root = [1,2,3,null,4], x = 2, y = 3
       1
      / \
     2   3
     \
      4
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.

---

解题过程

当且仅当一对节点深度相同而父节点不相同时，它们是堂兄弟节点。
dfs 深度优先遍历，过程中记录 x, y 的层次和父节点到全局变量，最后比较给出结果。
时间复杂度 O(n)，空间复杂度 O(n)

private static class SolutionV2020 {
    private Integer xLevel, yLevel;
    private Integer xParent, yParent;
    public boolean isCousins(TreeNode root, int x, int y) {
        if (null == root) {
            return false;
        }
        xLevel = null;
        yLevel = null;
        xParent = null;
        yParent = null;
        dfs(root, x, y, 0);
        return xLevel != null && xParent != null && xLevel.equals(yLevel) && !xParent.equals(yParent);
    }

    // 深度优先遍历，height是根节点root的高度
    private void dfs(TreeNode root, int x, int y, int height) {
        if (null == root) {
            return;
        }
        if (root.left != null) {
            if (root.left.val == x) {
                xLevel = height + 1;
                xParent = root.val;
            }
            if (root.left.val == y) {
                yLevel = height + 1;
                yParent = root.val;
            }
            dfs(root.left, x, y, height + 1);
        }
        if (root.right != null) {
            if (root.right.val == x) {
                xLevel = height + 1;
                xParent = root.val;
            }
            if (root.right.val == y) {
                yLevel = height + 1;
                yParent = root.val;
            }
            dfs(root.right, x, y, height + 1);
        }
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_993_CousinsInBinaryTree.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_993_CousinsInBinaryTree.java

---