Alex Blog

993. Cousins in Binary Tree

2019/10/14 Leetcode

993. 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
Output: false

Example 2:

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

Example 3:

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

 

Note:

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

Solution

// Recursive 100% 100%
class Solution {
    public boolean isCousins(TreeNode root, int x, int y) {
        return (findDepth(root, x, 1) == findDepth(root, y, 1)) && !isSibling(root, x, y);
    }
    
    // Preorder traversal
    private int findDepth(TreeNode node, int val, int height) {
        if (node == null) return 0;
        if (node.val == val) return height;
        return findDepth(node.left, val, height+1)|findDepth(node.right, val, height+1);
    }
    
    private boolean isSibling(TreeNode node, int x, int y) {
        if (node == null) return false;
        boolean current = false;
        if (node.left != null && node.right != null) {
            current = (node.left.val == x && node.right.val == y) || (node.left.val == y && node.right.val == x);
        }
        return current || isSibling(node.left, x, y) || isSibling(node.right, x, y);
    }
}

// BFS, level order traversal, 
// check isSibling and isSameLevel on different level
// 69% 100%
class Solution {
    public boolean isCousins(TreeNode root, int x, int y) {
        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null) return false;
        queue.offer(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            boolean foundX = false, foundY= false;
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.val == x) foundX = true;
                if (node.val == y) foundY = true;
                
                // check next level for sibling, if so return false
                // so that on each level, make sure isSibling doesn't exist
                if (node.left != null && node.right != null) {
                    if ((node.left.val == x && node.right.val == y) || node.left.val == y && node.right.val == x)
                        return false;
                }
                
                // previous level checked not isSibling
                // current level check isSameLevel
                if (foundX && foundY) return true;
                
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            
        }
        return false;
    }
}

// check isSibling and isSameLevel on same level, ignore root. Easier to understand
// 69% 100%
class Solution {
    public boolean isCousins(TreeNode root, int x, int y) {
        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null) return false;
        queue.offer(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            boolean foundX = false, foundY= false, isSibling = false;
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    if (node.left.val ==  x) foundX = true;
                    if (node.left.val == y) foundY = true;
                }
                if (node.right != null) {
                    if (node.right.val ==  x) foundX = true;
                    if (node.right.val == y) foundY = true;
                }
                

                if (node.left != null && node.right != null) {
                    if ((node.left.val == x && node.right.val == y) || node.left.val == y && node.right.val == x)
                        isSibling = true;
                }
                
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            // end of each level
            if (foundX && foundY && !isSibling) return true;
            
        }
        return false;
    }
}

Search

    Table of Contents