LeetCode #951 FlipEquivalentBinaryTrees. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접,연결리스트
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Flip Equivalent Binary Trees.
Memory Usage: 11.7 MB, less than 57.14% of C++ online submissions for Flip Equivalent Binary Trees.
LeetCode #951
Q.
For a binary tree T, we can define a flip operation as follows: choose any node, and swap the left and right child subtrees.
A binary tree X is flip equivalent to a binary tree Y if and only if we can make X equal to Y after some number of flip operations.
Write a function that determines whether two binary trees are flip equivalent. The trees are given by root nodes root1 and root2.
바이너리 트리 T 에서, 뒤집는 연산을 다음과 같이 정의할 수 있다 : 어느 노드를 정하고, 왼쪽과 오른쪽의 하위 트리의 자리를 교체한다.
만약 X 와 Y 를 몇번의 뒤집는 연산을 통해서 똑같이 만들 수 있다면, 바이너리 트리 X 는 바이너리 트리 Y 와 뒤집기동등하다고 할 수 있다.
두개의 바이너리 트리들이 뒤집기동등인지 아닌지 판별하는 함수를 써봐라. root 노드로 1, 2 가 주어진다.
Example 1:
Input:
root1 = [1,2,3,4,5,6,null,null,null,7,8],
root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7]
Output: true
Explanation: We flipped at nodes with values 1, 3, and 5.
Note:
- Each tree will have at most 100 nodes.
- Each value in each tree will be a unique integer in the range [0, 99].
노트:
1. 각 트리는 최대 100개의 노드들을 갖는다.
2. 각 트리의 값들은 중복되지 않고 0~ 99 정수 범위 안에 있다.
Process (Basic concept w/o exception handling)
// Process
//1. Input two TreeNodes
//2. Do if first nodes have same value
// 2.1 Recursive compare nodes
//3. Return result
// bool RecursiveNodeCompare(node1, node2)
//1. Input TreeNodes
// 2.1. Check node1's left node val is same with node2's left or right val
// 2.1.1. If same with node2's left val -> RecursiveNodeCompare(left1, left2)
// 2.1.2. If same with node2's right val -> RecursiveNodeCompare(left1, right2)
// 2.2. Check node1's right node val is same with node2's left or right val
// 2.2.1. If same with node2's left val -> RecursiveNodeCompare(right1, left2)
// 2.2.2. If same with node2's right val -> RecursiveNodeCompare(right1, right2)
//3. Return result
// 처리과정
//1. 2개의 루트노드 입력받는다.
//2. 둘다 null 이 아니면 -> 재귀함수 호출한다.
//3. 결과 반환한다.
// 재귀함수
//1. 2개의 노드 입력받는다.
//2. 입력받은 2개의 노드 하위 노드값들이 같은지 확인하면서 재귀호출한다.
//3. 결과 반환한다.
Code.. lemme see example code!!!
코드.. 예제코드를 보자!!!
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool flipEquiv(TreeNode* root1, TreeNode* root2) {
bool result = false;
if (root1 != 0 && root2 != 0) {
if (root1->val == root2->val) {
result = RecursiveNodeCompare(root1, root2);
}
} else if (root1 == 0 && root2 == 0) {
result = true;
}
return result;
}
bool RecursiveNodeCompare(TreeNode* node1, TreeNode* node2) {
bool result = false;
if (node1->left != 0 && node2->left != 0 && node1->right != 0 && node2->right != 0) {
if (node1->left->val == node2->left->val) {
if (RecursiveNodeCompare(node1->left, node2->left)) {
if (node1->right->val == node2->right->val) {
if (RecursiveNodeCompare(node1->right, node2->right)) {
result = true;
}
}
}
}
if (node1->left->val == node2->right->val) {
if (RecursiveNodeCompare(node1->left, node2->right)) {
if (node1->right->val == node2->left->val) {
if (RecursiveNodeCompare(node1->right, node2->left)) {
result = true;
}
}
}
}
}
else if (node1->left == 0 && node2->left == 0 && node1->right != 0 && node2->right != 0) {
if (node1->right->val == node2->right->val) {
if (RecursiveNodeCompare(node1->right, node2->right)) {
result = true;
}
}
}
else if (node1->right == 0 && node2->right == 0 && node1->left != 0 && node2->left != 0) {
if (node1->left->val == node2->left->val) {
if (RecursiveNodeCompare(node1->left, node2->left)) {
result = true;
}
}
}
else if (node1->left == 0 && node2->right == 0 && node1->right != 0 && node2->left != 0) {
if (node1->right->val == node2->left->val) {
if (RecursiveNodeCompare(node1->right, node2->left)) {
result = true;
}
}
}
else if (node1->right == 0 && node2->left == 0 && node1->left != 0 && node2->right != 0) {
if (node1->left->val == node2->right->val) {
if (RecursiveNodeCompare(node1->left, node2->right)) {
result = true;
}
}
}
else if (node1->right == 0 && node2->left == 0 && node1->left == 0 && node2->right == 0) {
result = true;
}
return result;
}
};
Something else you might like...?
2019/02/19 - [Life/Health care] - Lysine 라이신 usage/side effects/dosage 효과/효능/부작용/성인,소아 용법, 복용법
2019/02/28 - [Life/Health care] - Vitamin K, 비타민 K usage/side effects/dosage 효능/부작용/성인,소아 용법
