시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
이진 트리와 특정 노드 또는 키가 주어집니다. 주어진 조상 인쇄 이진 트리 재귀없는 노드.
차례
예
입력 :
키 = 7
출력 : 3 1
입력 :
키 = 4
출력 : 2 1
주어진 이진 트리 노드의 조상을위한 알고리즘
- 데이터를 보유 할 정수 변수와 왼쪽과 오른쪽 두 개의 Node 유형 객체를 포함하는 클래스 Node를 만듭니다. 정수 값을 매개 변수로 받아들이는 매개 변수화 된 생성자를 내부에 만들고 클래스 노드의 정수 변수에 저장합니다.
- 그런 다음 트리의 루트 노드와 키를 매개 변수로 받아들이는 주어진 키의 조상을 인쇄하는 함수를 만듭니다.
- 루트가 null인지 확인하고 반환합니다. 그렇지 않으면 노드 유형의 스택 데이터 구조를 만듭니다.
- 주어진 바이너리 탐색 시작 나무.
- 루트가 null과 같지 않고 루트의 데이터가 주어진 키와 같지 않은 동안 스택에서 루트를 푸시하고 루트를 루트의 왼쪽으로 업데이트합니다.
- 루트가 null이 아니고 루트의 데이터가 주어진 키와 같으면 루프를 중단하십시오.
- 그렇지 않으면 스택 맨 위에있는 노드의 오른쪽이 null과 같으면 스택 맨 위에있는 노드에서 루트를 업데이트하고 스택 맨 위에 팝니다. 스택이 비어 있지 않고 스택 맨 위에있는 노드의 오른쪽이 루트와 같지만 스택 맨 위에있는 노드에서 루트를 업데이트하고 스택.
- 스택이 비어있는 경우 루트를 null로 업데이트하고 그렇지 않으면 루트를 스택 맨 위에있는 노드의 오른쪽으로 업데이트합니다.
- 스택이 비어 있지 않은 동안 스택 상단에 노드의 데이터를 인쇄하고 스택 상단을 팝합니다.
주어진 이진 트리 노드의 조상을위한 C ++ 프로그램
#include <bits/stdc++.h>
using namespace std;
struct Node{
int data;
struct Node *left, *right;
};
struct Node* newNode(int data){
struct Node* node = (struct Node*) malloc(sizeof(struct Node));
node->data = data;
node->left = node->right = NULL;
return node;
}
void printAncestors(struct Node *root, int key){
if(root == NULL){
return;
}
stack<struct Node* > st;
while(1){
while(root && root->data != key){
st.push(root);
root = root->left;
}
if(root && root->data == key){
break;
}
if(st.top()->right == NULL){
root = st.top();
st.pop();
while(!st.empty() && st.top()->right == root){
root = st.top();
st.pop();
}
}
root = st.empty()? NULL: st.top()->right;
}
while(!st.empty()){
cout<<st.top()->data<<" ";
st.pop();
}
}
int main(){
struct Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);
int key = 7;
printAncestors(root, key);
return 0;
}
3 1
주어진 이진 트리 노드의 조상을위한 자바 프로그램
import java.util.Stack;
class findAncestors{
static class Node{
int data;
Node left,right;
Node(int data){
this.data = data;
}
}
static void printAncestors(Node root,int key){
if(root == null){
return;
}
Stack<Node> st = new Stack<>();
while(true){
while(root != null && root.data != key){
st.push(root);
root = root.left;
}
if(root != null && root.data == key){
break;
}
if(st.peek().right == null){
root =st.peek();
st.pop();
while( st.empty() == false && st.peek().right == root){
root = st.peek();
st.pop();
}
}
root = st.empty() ? null : st.peek().right;
}
while(!st.empty()){
System.out.print(st.peek().data+" ");
st.pop();
}
}
public static void main(String[] args){
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
int key = 7;
printAncestors(root, key);
}
}
3 1
복잡성 분석
시간 복잡성 : O (n) 여기서 n은 삽입 된 노드의 수입니다.
공간 복잡성 : O (n)은 n 개의 노드에 공간을 사용했기 때문입니다.
