LeetCode - Easy - 993. Cousins in Binary Tree

喜欢ヅ旅行 2022-10-05 09:48 109阅读 0赞

## Topic ##

*  Tree
 *  Breadth-first Search
 *  Depth-first Search

## Description ##

[https://leetcode.com/problems/cousins-in-binary-tree/][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:**

![d38789084a1b97428f0987304b0f0182.png][]

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

**Example 2:**

![81a1925728a3e6d04c3c05bddda1630c.png][]

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

**Example 3:**

![5fbda38597d33da62b878227e715aa2a.png][]

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));
    	}
    }

[https_leetcode.com_problems_cousins-in-binary-tree]: https://leetcode.com/problems/cousins-in-binary-tree/
[d38789084a1b97428f0987304b0f0182.png]: /images/20221005/bd34bcfc10884dd6ba57bcc986305f94.png
[81a1925728a3e6d04c3c05bddda1630c.png]: /images/20221005/4891225adfb94357a0e8f2c56a0501ea.png
[5fbda38597d33da62b878227e715aa2a.png]: /images/20221005/69c9af3677b2466299e619beb5a9d372.png