Tree / Binary Search Tree
Find Minimum Depth of a Binary Tree
Recursive하게 탐색을 하는데 현재 노드가 leaf 노드라면 1을 리턴한다.
그게 아니고 왼쪽 자식이 없고 오른쪽만 있으면 오른쪽에서 받은 recursion+1을 리턴한다.
반대의 경우도 마찬가지로 한다.
마지막으로 양쪽 자식이 다 있으면 그중 양쪽 recursion의 최솟값을 리턴한다.
Maximum Path Sum in a Binary Tree
아무 노드에서부터 아무 노드까지의 path를 봤을 때 그 노드들이 갖고 있는 값들의 합이 최대가 되도록 해야 한다.
음의 값도 가질 수 있다.
루트부터 자식 노드들로 recursive하게 진행을 한다.
각 노드에서 가질 수 있는 경우는 네 가지이다.
지금 노드만 갖고 있는 경우, 지금 노드와 왼쪽 recursion의 합인 경우, 지금 노드와 오른쪽 recursion의 합인 경우, 지금 노드와 양쪽 recursion의 합인 경우 이렇게 네 가지 이다.
이 네 가지 중 최댓값 myResult를 구한 뒤, global variable인 result에 result = max(result, myResult)를 저장해주면서 업데이트한다.
Check If a Given Array Can Represent Preorder Traversal of Binary Search Tree
각 노드에 대해 타당성을 확인한다.
지금 index의 값을 기준으로, 오른쪽 subarray를 봤을 때 자기보다 큰 값이 있으면, 그 이후에는 자기보다 작은 게 나오면 안된다.
n제곱 알고리즘이지만 stack을 활용하면 n알고리즘으로 만들 수 있다.
https://www.geeksforgeeks.org/check-if-a-given-array-can-represent-preorder-traversal-of-binary-search-tree/
Check Whether a Binary Tree Is a Full Binary Tree or Not
Full binary tree란 모든 노드가 자식 노드가 아예 없거나 있으면 반드시 두 개가 있는 트리이다.
루트부터 recursive하면서 null이거나 양쪽 다 자식이 없으면 true를 리턴한다.
양쪽 중 하나가 있으면 양쪽 각각에 대해 && 연산한 것을 리턴한다.
나머지는 false이다.
Bottom View of a Binary Tree
https://www.geeksforgeeks.org/bottom-view-binary-tree/
Remove Nodes on a Root to Leaf Paths of Length < K
루트부터 시작해서 리프로 가는 각 path가 있을텐데 그중 path 길이가 k 미만인 노드들을 다 지워야 한다.
postorder traversal로 하여 리프부터 지울 건 지우면서 올라온다.
각 노드에서 리프이고 지울 상황이면 지우고, 그게 아니라 한 쪽에 다른 자식이 있고 그 자식이 k이상을 보장한다면 지우지 않는다.
Lowest Common Ancestor in a Binary Search Tree
n1과 n2가 주어졌을 때 lowest common ancestor를 찾아야 한다.
루트부터 traverse하면서 n1과 n2 사이의 값을 처음 만나던가, 혹은 n1이나 n2 중 하나의 값을 만나면 그게 LCA이다.
Check If a Binary Tree Is a Subtree of Another Binary Tree
각각의 inorder과 preorder 결과를 저장한 다음에 둘 다 어느 하나의 subarray인지를 확인한다.
Reverse Alternate Levels of a Perfect Binary Tree
Perfect binary tree가 주어졌을 때 짝수 level의 노드들을 좌우 반전 시켜야 한다.
Inorder traverse를 하면서 짝수번째 원소들만 따로 저장을 하고 그 저장된 array를 뒤집어준다.
그다음 그 트리를 다시 traverse하면서 짝수번째때 reversed array에서 읽어서 값을 바꾼다
--------------------------------------------------------------------------
Reference
https://www.geeksforgeeks.org/top-10-algorithms-in-interview-questions/#algo5
Recursive하게 탐색을 하는데 현재 노드가 leaf 노드라면 1을 리턴한다.
그게 아니고 왼쪽 자식이 없고 오른쪽만 있으면 오른쪽에서 받은 recursion+1을 리턴한다.
반대의 경우도 마찬가지로 한다.
마지막으로 양쪽 자식이 다 있으면 그중 양쪽 recursion의 최솟값을 리턴한다.
Maximum Path Sum in a Binary Tree
아무 노드에서부터 아무 노드까지의 path를 봤을 때 그 노드들이 갖고 있는 값들의 합이 최대가 되도록 해야 한다.
음의 값도 가질 수 있다.
루트부터 자식 노드들로 recursive하게 진행을 한다.
각 노드에서 가질 수 있는 경우는 네 가지이다.
지금 노드만 갖고 있는 경우, 지금 노드와 왼쪽 recursion의 합인 경우, 지금 노드와 오른쪽 recursion의 합인 경우, 지금 노드와 양쪽 recursion의 합인 경우 이렇게 네 가지 이다.
이 네 가지 중 최댓값 myResult를 구한 뒤, global variable인 result에 result = max(result, myResult)를 저장해주면서 업데이트한다.
Check If a Given Array Can Represent Preorder Traversal of Binary Search Tree
각 노드에 대해 타당성을 확인한다.
지금 index의 값을 기준으로, 오른쪽 subarray를 봤을 때 자기보다 큰 값이 있으면, 그 이후에는 자기보다 작은 게 나오면 안된다.
n제곱 알고리즘이지만 stack을 활용하면 n알고리즘으로 만들 수 있다.
https://www.geeksforgeeks.org/check-if-a-given-array-can-represent-preorder-traversal-of-binary-search-tree/
Check Whether a Binary Tree Is a Full Binary Tree or Not
Full binary tree란 모든 노드가 자식 노드가 아예 없거나 있으면 반드시 두 개가 있는 트리이다.
루트부터 recursive하면서 null이거나 양쪽 다 자식이 없으면 true를 리턴한다.
양쪽 중 하나가 있으면 양쪽 각각에 대해 && 연산한 것을 리턴한다.
나머지는 false이다.
Bottom View of a Binary Tree
https://www.geeksforgeeks.org/bottom-view-binary-tree/
Remove Nodes on a Root to Leaf Paths of Length < K
루트부터 시작해서 리프로 가는 각 path가 있을텐데 그중 path 길이가 k 미만인 노드들을 다 지워야 한다.
postorder traversal로 하여 리프부터 지울 건 지우면서 올라온다.
각 노드에서 리프이고 지울 상황이면 지우고, 그게 아니라 한 쪽에 다른 자식이 있고 그 자식이 k이상을 보장한다면 지우지 않는다.
Lowest Common Ancestor in a Binary Search Tree
n1과 n2가 주어졌을 때 lowest common ancestor를 찾아야 한다.
루트부터 traverse하면서 n1과 n2 사이의 값을 처음 만나던가, 혹은 n1이나 n2 중 하나의 값을 만나면 그게 LCA이다.
Check If a Binary Tree Is a Subtree of Another Binary Tree
각각의 inorder과 preorder 결과를 저장한 다음에 둘 다 어느 하나의 subarray인지를 확인한다.
Reverse Alternate Levels of a Perfect Binary Tree
Perfect binary tree가 주어졌을 때 짝수 level의 노드들을 좌우 반전 시켜야 한다.
Inorder traverse를 하면서 짝수번째 원소들만 따로 저장을 하고 그 저장된 array를 뒤집어준다.
그다음 그 트리를 다시 traverse하면서 짝수번째때 reversed array에서 읽어서 값을 바꾼다
--------------------------------------------------------------------------
Reference
https://www.geeksforgeeks.org/top-10-algorithms-in-interview-questions/#algo5
댓글
댓글 쓰기