Apes Together Strong.

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/description/ 주어진 트리에서 두개의 target 노드 중, 가장 낮은 위치의 공통 부모 노드를 찾아라. 특정 노드간의 경로를 우선 기록한다. 그리고 두 노드 경로를 비교해서 달라지기 시작하면, 그 바로 직전 노드가 가장 낮은 공통 부모다.  코드.더보기bool collectPathToNode(TreeNode* node, TreeNode* target, vector& vBuff){ if (node == nullptr) return false; vBuff.push_back(node); if (node == target) ..

https://leetcode.com/problems/subtree-of-another-tree/description/ 주어진 두개의 tree가 있을 때, 하나의 트리중 일부가 다른 트리와 동일한지 판단하라. 모든 노드에 대해 subRoot tree와 같은지 비교하면 될 것이다.  이러면 두번 돌게 되는데...  단일 pass에 모두 처리하는 방법에 대해 고민 필요. 코드. 더보기void isSameTreeHelper(TreeNode* nodeA, TreeNode* nodeB, bool& same){ if (!same) return; if (nodeA == nullptr && nodeB == nullptr) return; if ((nodeA == nullptr && nod..

https://leetcode.com/problems/same-tree/description/ 주어진 두개의 트리가 동일한지 확인하라.  두 트리의 원소의 모든 값을 대조한다. 코드더보기void isSameTreeHelper(TreeNode* nodeA, TreeNode* nodeB, bool& same){ if(!same) return; if(nodeA==nullptr && nodeB==nullptr) return; if((nodeA==nullptr && nodeB!=nullptr) || (nodeA!=nullptr && nodeB==nullptr)) { same = false; return; } if(nodeA->val != n..

https://leetcode.com/problems/balanced-binary-tree/description/ 주어진 이진트리가 balanced binary tree인지 판단하라.  balanced 이진트리가 정확하게 무엇인지 먼저 재정의 해 보자. 특정 노드 기준으로 depth차가 최대 1이어야 한다. 다음 그림에서 dv 가  특정 노드에서 depth차를 의미한다.  아래 노드는 B 노드가 dv 2로 만족하지 않는다.  따라서 특정 노드에서 양 child 최대 depth를 구하고 그 차가 1보다 같거나 작은지 판단한다.  코드.더보기int isBalancedDFS(bool& isBalanced, TreeNode* node){ if (!isBalanced) return isBalan..

https://leetcode.com/problems/diameter-of-binary-tree/description/  주어진 tree의 최대 diameter 길이를 구하라.diameter란 두 leaf 노드 간 최대 거리를 말하며, 이는 root를 거치지 않을 수 있다. 특정 노드를 기준으로 left child와 right child의 max count가 diameter가 된다. 이 diameter를 모든 노드 기준으로 구하고, 그 중 max 값을 반환한다.  문제는 이 연산을 child count를 구하는 것과 (최적화를 위해) 동시에 처리해야 한다는 것이다.이것으로 Easy보다는 Medium에 가까운 문제.  코드 더보기int diameterOfBinaryTreeDFS(int& maxDiamete..

https://leetcode.com/problems/maximum-depth-of-binary-tree/description/ 주어진 binary tree의 최대 depth 를 구하라.  DFS 식으로 최대 depth를 카운팅 한다. 코드  int maxDepthDFS(TreeNode* node){ if (node == nullptr) return 0; int left = maxDepth(node->left) + 1; int right = maxDepth(node->right) + 1; return max(left, right);}int maxDepth(TreeNode* root) { return maxDepthDFS(root);}  결과