Apes Together Strong.

https://leetcode.com/problems/validate-binary-search-tree/description/ 주어진 tree가 유효한 이진 트리인지 판단하라. 우선 이진 트리에 조건을 생각해 볼 필요가 있다. 위 그림처럼, node값은 늘, left 와 right 의 사이 값을 가져야 한다.이 문제가 child 가 생기면 복잡해 진다. 위 그림처럼, 노드에서 조건을 만족해도 전체 트리에서는 만족하지 않게 될 수 있다. 즉, 정리하면 특정 노드 기준으로 left node 중 최대값, right node 중 최소값 사이에 노드값이 존재해야 한다. 따라서 특정 노드에서 모든 차일드 노드를 순회해서 left의 최대값, right의 최소값 을 구한 후 현재 노드가 이 값 사이에 있나 확인한다. ..

https://leetcode.com/problems/count-good-nodes-in-binary-tree/description/ 주어진 Binary Tree에서 good node의 수를 찾아라. good node는 root와 해당 노드 사이에 자신보다 큰 수가 없어야 한다. 특정 노드를 기준으로 root와 자신 사이에 max value를 구한다. 이 값이 node->val 보다 같거나 작으면 조건을 만족하는 것이다.  노드의 중복 탐색을 피하기 위해 자신을 포함하여 max value를 재 계산하고 다시 child로 내려가 조건 검사를 이어 간다.  코드 더보기void goodNodesHelper(int& cnt, int maxV, TreeNode* node){ if (node == nullpt..

https://leetcode.com/problems/binary-tree-right-side-view/description/ 주어진 tree의 각 level의 마지막 값을 구하라.   level order traversal을 한 후 제일 마지막 값만을 취한다. 코드더보기vector rightSideView(TreeNode* root) { vector vRet; if (root == nullptr) return vRet; queue qBuff; qBuff.push(root); while (qBuff.size() > 0) { int cnt = qBuff.size(); for (int q = 0; q val); ..

https://leetcode.com/problems/binary-tree-level-order-traversal/description/ 주어진 binary tree를 level order 탐색하라. 사실상 easy 난이도 문제.BS의 기본 문제, 다른 문제들로 응용에 잘 나옴.  코드 더보기vector> levelOrder(TreeNode* root) { vector> vRet; if (root == nullptr) return vRet; queue qBuff; qBuff.push(root); while (qBuff.size() > 0) { vector vBuff; int cnt = qBuff.size(); for (in..