0993 updated.

liuyubobobo · liuyubobobo · commit 2b6d1a435123 · 2019-02-18T17:12:35.000-08:00
diff --git a/0993-Cousins-in-Binary-Tree/cpp-0993/CMakeLists.txt b/0993-Cousins-in-Binary-Tree/cpp-0993/CMakeLists.txt
@@ -1,6 +1,6 @@
 cmake_minimum_required(VERSION 3.13)
-project(cpp_0993)
+project(A)
 
 set(CMAKE_CXX_STANDARD 11)
 
-add_executable(cpp_0993 main.cpp)
+add_executable(A main2.cpp)
diff --git a/0993-Cousins-in-Binary-Tree/cpp-0993/main.cpp b/0993-Cousins-in-Binary-Tree/cpp-0993/main.cpp
@@ -1,6 +1,67 @@
+/// Source : https://leetcode.com/problems/cousins-in-binary-tree/
+/// Author : liuyubobobo
+/// Time   : 2019-02-16
+
 #include <iostream>
+#include <cassert>
+
+using namespace std;
+
+
+/// Two-Pass DFS
+/// Time Complexity: O(n)
+/// Space Complexity: O(h)
+
+/// 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 isCousins(TreeNode* root, int x, int y) {
+
+        if(!root || root->val == x || root->val == y)
+            return false;
+
+        pair<int, int> p1; // depth, parent
+        if(!dfs(root, x, 0, p1)) return false;
+
+        pair<int, int> p2;
+        if(!dfs(root, y, 0, p2)) return false;
+
+        return p1.first == p2.first && p1.second != p2.second;
+    }
+
+private:
+    bool dfs(TreeNode* node, int x, int d, pair<int, int>& p){
+
+        if(node->left && node->left->val == x){
+            p = make_pair(d + 1, node->val);
+            return true;
+        }
+
+        if(node->right && node->right->val == x){
+            p = make_pair(d + 1, node->val);
+            return true;
+        }
+
+        if(node->left && dfs(node->left, x, d + 1, p))
+            return true;
+
+        if(node->right && dfs(node->right, x, d + 1, p))
+            return true;
+
+        return false;
+    }
+};
+
 
 int main() {
-    std::cout << "Hello, World!" << std::endl;
+
     return 0;
 }
diff --git a/0993-Cousins-in-Binary-Tree/cpp-0993/main2.cpp b/0993-Cousins-in-Binary-Tree/cpp-0993/main2.cpp
@@ -0,0 +1,59 @@
+/// Source : https://leetcode.com/problems/cousins-in-binary-tree/
+/// Author : liuyubobobo
+/// Time   : 2019-02-18
+
+#include <iostream>
+#include <cassert>
+#include <unordered_map>
+
+using namespace std;
+
+
+/// One-Pass DFS
+/// Using HashMap to record the result :-)
+///
+/// Time Complexity: O(n)
+/// Space Complexity: O(n)
+
+/// 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 isCousins(TreeNode* root, int x, int y) {
+
+        if(!root || root->val == x || root->val == y)
+            return false;
+
+        unordered_map<int, pair<int, int>> record; // depth, parent
+        dfs(root, 0, record);
+
+        return record[x].first == record[y].first && record[x].second != record[y].second;
+    }
+
+private:
+    void dfs(TreeNode* node, int d, unordered_map<int, pair<int, int>>& record){
+
+        if(node->left) {
+            record[node->left->val] = make_pair(d + 1, node->val);
+            dfs(node->left, d + 1, record);
+        }
+
+        if(node->right){
+            record[node->right->val] = make_pair(d + 1, node->val);
+            dfs(node->right, d + 1, record);
+        }
+    }
+};
+
+
+int main() {
+
+    return 0;
+}
