From 8fb3943122786e9ab13bf06cae6ad9ab70860fc4 Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Fri, 11 Jan 2019 19:54:13 -0600
Subject: Tree height partially done.

Partially because it didn't pass time limitations for test case 19 out
of 24. I suspect it's pointer reference stuff that was the cause of the
issue. Checking in for now, I need to research and learn more and will
tackle this again so it passes all tests.---
 Sources/DataStructure.cpp | 185 ++++++++++++++++++++++------------------------
 1 file changed, 90 insertions(+), 95 deletions(-)

diff --git a/Sources/DataStructure.cpp b/Sources/DataStructure.cpp
index 1360ef5..b82f908 100644
--- a/Sources/DataStructure.cpp
+++ b/Sources/DataStructure.cpp
@@ -1,115 +1,110 @@
 #include <iostream>
-#include <stack>
+#include <queue>
 #include <algorithm>
 #include <vector>
 //#include <gtest/gtest.h>
 
-using std::string;
-using std::stack;
+using std::vector;
+using std::queue;
 
-const std::vector<char> brackets = {'[',']','(',')','{','}'};
+class Node;
 
-static string checkBracket(string exp) {
-    stack<char> charStack;
-    int unmatchedOpeningBracket = 0;
-    int count = 0;
-    for (int i = 0; i < exp.length(); i++) {
-        char c = exp[i];
-        if (!(std::find(brackets.begin(), brackets.end(), c) !=brackets.end())) {
-            count = count + 1;
-            continue;
-        }
+class Node {
+public:
+	int key;
+	Node *parent;
+	vector<Node *> children;
 
-        if (c == '[' || c == '(' || c == '{') {
-            charStack.push(c);
-            count = count + 1;
-            unmatchedOpeningBracket = count;
-        } else {
-            if (charStack.empty())
-                return std::to_string(i+1);
-            char top = charStack.top();
-            charStack.pop();
-            if ((top == '[' && c != ']') || (top == '(' && c != ')') || (top == '{' && c != '}')) {
-                return std::to_string(i+1);
-            } else {
-                unmatchedOpeningBracket = unmatchedOpeningBracket - 1;
-            }
-            count = count + 1;
-        }
-    }
-    if (charStack.empty())
-        return "Success";
-    else if (unmatchedOpeningBracket > 0) {
-        return std::to_string(unmatchedOpeningBracket);
-    }
-    return std::to_string(count);
+	Node() {
+		this->parent = NULL;
+	}
+
+	void setParent(Node *theParent) {
+		parent = theParent;
+		parent->children.push_back(this);
+	}
+
+	vector<Node *> getChildren() {
+		return children;
+	}
+
+	void setKey(int theKey) {
+		key = theKey;
+	}
+};
+
+int treeLevelCounter(vector<Node> &nodes, int rootIndex) {
+	int levelCounter = 1;
+	queue<Node *> q;
+	int popCount = 0;
+	int childrenCount = nodes[rootIndex].getChildren().size();
+	int grandChildrenCount = 0;
+	for (int i = 0; i < childrenCount; i++) {
+		q.push(nodes[rootIndex].getChildren()[i]);
+	}
+	while (!q.empty()) {
+		if (popCount < childrenCount) {
+			Node *n = q.front();
+			q.pop();
+			int i = n->children.size();
+			if (i != 0) {
+				for (int j = 0; j < i; j++) {
+					q.push(n->children[j]);
+				}
+			}
+			grandChildrenCount = grandChildrenCount + i;
+			popCount = popCount + 1;
+		} else {
+			popCount = 0;
+			childrenCount = grandChildrenCount;
+			grandChildrenCount = 0;
+			levelCounter = levelCounter + 1;
+		}
+	}
+	return levelCounter + 1;
+}
+int getHeight(vector<int> &a) {
+	vector<Node> nodes;
+	nodes.resize(a.size());
+	int rootIndex = 0;
+	for (int i = 0; i < a.size(); i++) {
+		int parentIndex = a[i];
+		nodes[i].setKey(i);
+		if (parentIndex == -1) {
+			rootIndex = i;
+		} else {
+			nodes[i].setParent(&nodes[parentIndex]);
+		}
+	}
+	return treeLevelCounter(nodes, rootIndex);
 }
 
-//TEST(CheckBracket, t1) {
-//    string exp = "[]";
-//    ASSERT_EQ("Success", checkBracket(exp));
-//}
-//
-//TEST(CheckBracket, t2) {
-//    string exp = "{}[]";
-//    ASSERT_EQ("Success", checkBracket(exp));
-//}
-//
-//TEST(CheckBracket, t3) {
-//    string exp = "[()]";
-//    ASSERT_EQ("Success", checkBracket(exp));
+//TEST(GetTreeHeight, t1) {
+//    vector<int> a = {4, -1, 4, 1, 1};
+//    ASSERT_EQ(3, getHeight(a));
 //}
 //
-//TEST(CheckBracket, t4) {
-//    string exp = "(())";
-//    ASSERT_EQ("Success", checkBracket(exp));
+//TEST(GetTreeHeight, t2) {
+//    vector<int> a = {-1, 0, 4, 0, 3};
+//    ASSERT_EQ(4, getHeight(a));
 //}
 //
-//TEST(CheckBracket, t5) {
-//    string exp = "{[]}()";
-//    ASSERT_EQ("Success", checkBracket(exp));
+//TEST(GetTreeHeight, t3) {
+//    vector<int> a = {9, 7, 5, 5, 2, 9, 9, 9, 2, -1};
+//    ASSERT_EQ(4, getHeight(a));
 //}
 //
-//TEST(CheckBracket, t6) {
-//    string exp = "{";
-//    ASSERT_EQ("1", checkBracket(exp));
-//}
-//
-//TEST(CheckBracket, t7) {
-//    string exp = "{[}";
-//    ASSERT_EQ("3", checkBracket(exp));
-//}
-//
-//TEST(CheckBracket, t8) {
-//    string exp = "foo(bar);";
-//    ASSERT_EQ("Success", checkBracket(exp));
-//}
-//
-//TEST(CheckBracket, t9) {
-//    string exp = "foo(bar[i);";
-//    ASSERT_EQ("10", checkBracket(exp));
-//}
-//
-//TEST(CheckBracket, t10) {
-//    string exp = "[](()";
-//    ASSERT_EQ("3", checkBracket(exp));
-//}
-//
-//TEST(CheckBracket, t11) {
-//    string exp = "{[}haha";
-//    ASSERT_EQ("3", checkBracket(exp));
-//}
-//
-//TEST(CheckBracket, t12) {
-//    string exp = "haha{[}";
-//    ASSERT_EQ("7", checkBracket(exp));
+//TEST(GetTreeHeight, t4) {
+//    vector<int> a = {8, 8, 5, 6, 7, 3, 1, 6, -1, 5};
+//    ASSERT_EQ(6, getHeight(a));
 //}
 
 int main() {
-    std::string text;
-    getline(std::cin, text);
-
-    std::cout << checkBracket(text) << '\n';
-
-    return 0;
+	size_t an;
+	std::cin >> an;
+	vector<int> a(an);
+	for (size_t i = 0; i < an; i++) {
+		std::cin >> a[i];
+	}
+	std::cout << getHeight(a) << std::endl;
 }
-- 
cgit v1.2.3