트리순회11 [leetcode 543] Diameter of Binary Tree Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root. Example: Given a binary tree Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3]. 트리 지름 구하기. 같은 부모를 가진 노드 사이에 최대 거리 구하기 문제 풀이 - 항상 루트 노드를 지나야 최대 거리라고 생각해서 틀림! .. 2020. 10. 11. [leetcode 617] Merge Two Binary Trees Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree. 트리 합치기 풀이: - 기준이 되는 트리를 .. 2020. 10. 11. [leetcode 230] Kth Smallest Element in a BST k번째 숫자 찾기 방법 - 전체를 inorder로 순회해서 벡터에 담는다. - k번째 원소를 꺼낸다. class Solution { public: void Traverse(TreeNode* root, vector &inorder){ if(root == nullptr){ return; } Traverse(root->left, inorder); inorder.push_back(root->val); Traverse(root->right, inorder); } int kthSmallest(TreeNode* root, int k) { vectorinorder; Traverse(root, inorder); return inorder[k-1]; } }; - 더 빠른 방법 stack을 사용해서 inorder를 만든다... 2020. 10. 4. [leetcode 98] Validate Binary Search Tree root 노드를 중심으로 왼쪽 subtree는 전부 root 노드보다 값이 작아야 하고 오른쪽 subtree는 전부 root 노드보다 값이 커야 한다. - subtree에 있는 모든 노드가 조건을 만족해야 한다. - 같아도 안된다. 1) inorder를 이용한 방식-stack 사용 - stack을 사용하여 왼쪽 가장 아래 노드까지 내려간다. - subtree기준으로 어쨌든 오른쪽 노드가 가장 크면 되기 때문에 값의 크기를 비교한 후엔 현재노드를 right 노드로 설정한다. using namespace std; class Solution { public: bool isValidBST(TreeNode* root) { stacks; long long inorder = -LONG_MAX; while(!s.emp.. 2020. 10. 4. 이전 1 2 3 다음
