Leetcode
2020.04.30 11:47
993. Cousins in Binary Tree
조회 수 256 추천 수 0 댓글 0
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:
- The number of nodes in the tree will be between
2
and100
. - Each node has a unique integer value from
1
to100
.
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public boolean isCousins(TreeNode root, int x, int y) { if(root == null){ return false; } int depth = 0; int depth1 = 0; int depth2 = 0; TreeNode parent1 = null; TreeNode parent2 = null; Map<TreeNode, TreeNode> hmap = new HashMap<>(); Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); hmap.put(root, null); while(queue.size() > 0){ depth++; int size = queue.size(); for(int i=0; i<size; i++){ TreeNode node = queue.poll(); if(node.left != null){ queue.offer(node.left); hmap.put(node.left, node); } if(node.right != null){ queue.offer(node.right); hmap.put(node.right, node); } if(node.val == x){ depth1 = depth; parent1 = hmap.get(node); } if(node.val == y){ depth2 = depth; parent2 = hmap.get(node); } } } return parent1 != parent2 && depth1 == depth2; } }
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { Map<Integer, TreeNode> hmap; public boolean isCousins(TreeNode root, int x, int y) { hmap = new HashMap<>(); int depth1 = findDepth(root, x, 0); int depth2 = findDepth(root, y, 0); return hmap.get(x) != hmap.get(y) && depth1 == depth2; } public int findDepth(TreeNode node, int val, int depth){ if(node == null){ return 0; } if(node.left != null && node.left.val == val){ hmap.put(val, node); } if(node.right != null && node.right.val == val){ hmap.put(val, node); } if(node.val != val){ int left = findDepth(node.left, val, depth + 1); int right = findDepth(node.right, val, depth + 1); return Math.max(left, right); } return depth + 1; } }
[문제] https://leetcode.com/problems/cousins-in-binary-tree/
번호 | 분류 | 제목 | 글쓴이 | 날짜 | 조회 수 |
---|---|---|---|---|---|
77 | Leetcode | [todo] 687. Longest Univalue Path | hooni | 2020.05.01 | 238 |
76 | Programmers |
team game
![]() |
hooni | 2020.04.30 | 0 |
75 | Programmers |
hashmap
![]() |
hooni | 2020.04.30 | 0 |
74 | Programmers |
fib
![]() |
hooni | 2020.04.30 | 0 |
73 | Leetcode | 997. Find the Town Judge | hooni | 2020.05.02 | 761 |
72 | Leetcode |
994. Rotting Oranges
![]() |
hooni | 2020.04.14 | 212 |
» | Leetcode |
993. Cousins in Binary Tree
![]() |
hooni | 2020.04.30 | 256 |
70 | Leetcode | 973. K Closest Points to Origin | hooni | 2020.04.15 | 210 |
69 | Leetcode | 946. Validate Stack Sequences | hooni | 2020.04.08 | 194 |
68 | Leetcode | 937. Reorder Data in Log Files | hooni | 2020.04.25 | 200 |
67 | Leetcode | 897. Increasing Order Search Tree | hooni | 2020.05.04 | 725 |
66 | Leetcode | 876. Middle of the Linked List | hooni | 2020.05.04 | 711 |
65 | Leetcode |
872. Leaf-Similar Trees
![]() |
hooni | 2020.05.04 | 719 |
64 | Leetcode | 852. Peak Index in a Mountain Array | hooni | 2020.04.28 | 203 |
63 | Leetcode | 844. Backspace String Compare | hooni | 2020.05.05 | 824 |
62 | Leetcode | 783. Minimum Distance Between BST Nodes | hooni | 2020.05.01 | 768 |
61 | Leetcode | 763. Partition Labels | hooni | 2020.04.17 | 256 |
60 | Leetcode | 75. Sort Colors | hooni | 2020.04.14 | 184 |
59 | Leetcode | 731. My Calendar II | hooni | 2020.04.15 | 194 |
58 | Leetcode | 729. My Calendar I | hooni | 2020.04.15 | 187 |