LeetCode - Easy - 993. Cousins in Binary Tree-蒲公英云

LeetCode - Easy - 993. Cousins in Binary Tree

Topic

Tree
Breadth-first Search
Depth-first Search

Description

https://leetcode.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
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

Constraints:

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

Analysis

方法一：BFS

方法二：DFS

Submission

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import com.lun.util.BinaryTree.TreeNode;
public class CousinsInBinaryTree { 
    //方法一：BFS
    public boolean isCousins(TreeNode root, int x, int y) { 
        LinkedList<TreeNode> queue = new LinkedList<>();
        List<Integer> tempList = new ArrayList<>();
        queue.offer(root);
        int depth = 0;
        checkNode(null, root, x, y, depth, tempList);
        while(!queue.isEmpty()) { 
            depth++;
            for(int size = queue.size(); size > 0; size--) { 
                TreeNode node = queue.poll();
                if(node.left != null) { 
                    if(checkNode(node, node.left, x, y, depth, tempList))
                        return true;
                    queue.offer(node.left);
                }
                if(node.right != null) { 
                    if(checkNode(node, node.right, x, y, depth, tempList))
                        return true;
                    queue.offer(node.right);
                }
            }
        }
        return false;
    }
    private boolean checkNode(TreeNode parent, TreeNode child, int x, int y, int depth, List<Integer> list) { 
        if(child.val == x || child.val == y) { 
            list.add(parent == null? -1 : parent.val);
            list.add(depth);
        }
        if(list.size() == 4) { 
            //different parent and same depth
            if(list.get(0) != list.get(2) && list.get(1) == list.get(3))
                return true;
        }
        return false;
    }
    //方法二：DFS
    public boolean isCousins2(TreeNode root, int x, int y) { 
        return dfs(null, root, x, y, 0, new ArrayList<>());
    }
    private boolean dfs(TreeNode parent, TreeNode child, int x, int y, int depth, List<Integer> list) { 
        if(child == null) return false;
        if(child.val == x || child.val == y) { 
            list.add(parent == null ? -1 : parent.val);
            list.add(depth);
        }
        if(list.size() == 4) { 
            //if different parent and same depth is true, return true
            if(list.get(0) != list.get(2) && list.get(1) == list.get(3))
                return true;
        }
        return dfs(child, child.left, x, y, depth + 1, list) || // 
                dfs(child, child.right, x, y, depth + 1, list);
    }
}

Test

import static org.junit.Assert.*;
import org.junit.Test;
import com.lun.util.BinaryTree;
public class CousinsInBinaryTreeTest { 
    @Test
    public void test() { 
        CousinsInBinaryTree obj = new CousinsInBinaryTree();
        assertFalse(obj.isCousins(BinaryTree.integers2BinaryTree(1, 2, 3, 4), 4, 3));
        assertTrue(obj.isCousins(BinaryTree.integers2BinaryTree(1, 2, 3, null, 4, null, 5), 5, 4));
        assertFalse(obj.isCousins(BinaryTree.integers2BinaryTree(1, 2, 3, null, 4), 2, 3));
    }
    @Test
    public void test2() { 
        CousinsInBinaryTree obj = new CousinsInBinaryTree();
        assertFalse(obj.isCousins(BinaryTree.integers2BinaryTree(1, 2, 3, 4), 4, 3));
        assertTrue(obj.isCousins(BinaryTree.integers2BinaryTree(1, 2, 3, null, 4, null, 5), 5, 4));
        assertFalse(obj.isCousins(BinaryTree.integers2BinaryTree(1, 2, 3, null, 4), 2, 3));
    }
}