Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.
In Drzewo symetryczne problem, który daliśmy drzewo binarnesprawdź, czy jest lustrem samego siebie. Mówi się, że drzewo jest swoim lustrzanym odbiciem, jeśli istnieje oś symetrii przechodząca przez węzeł główny, który dzieli drzewo na dwie takie same połowy.
Spis treści
Przykład
Typy rozwiązań dla drzewa symetrycznego
- Rekurencyjne
- Iteracyjny
Rekurencyjne
Podejście
Używamy 2 kopii drzewa binarnego, powiedzmy b1 i b2 (do obsługi oddzielnie lewego i prawego poddrzewa) i sprawdzamy, czy:
- korzeń wartości b1 i b2 są takie same lub nie.
- lewo poddrzewo b1 i prawo poddrzewo b2 są takie same (zarówno pod względem struktury, jak i wartości węzłów), czy nie.
- prawo poddrzewo b1 i lewo poddrzewo b2 jest taka sama (zarówno pod względem struktury, jak i wartości węzłów), czy nie.
jeśli warunki 1,2, 3 i XNUMX są spełnione rekurencyjnie dla lewego i prawego poddrzewa zwracamy po prostu prawdę (w przeciwnym razie zwracamy fałsz).
b1 i b2 mają odpowiednio root1 i root2 jako węzeł główny.
Algorytm dla drzewa symetrycznego
- Utwórz dwie kopie drzewa binarnego (root1 i root2), aby oddzielnie obsługiwać lewe i prawe poddrzewo.
- Zdefiniuj przypadek podstawowy.
- Sprawdź, czy warunki wymienione powyżej (1,2, 3 i XNUMX) są spełnione, czy nie.
- Jeśli powyższe warunki są fałszywe, co oznacza, że jeden z elementów root1 lub root2 jest pusty, zwróć false.
Implementacja dla Symmetric Tree
Program C ++ dla drzewa symetrycznego
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
// defining the tree node
class Node
{
public :
int data;
Node *left;
Node *right;
// constructor for initialization
Node(int num)
{
data = num;
left = right = NULL;
}
};
/*utility function to check whether trees rooted at
root1 and root2 are mirror images of each other or not */
bool utility(Node *root1, Node *root2)
{
/* base case : if both trees are empty then
they are mirror images of each other */
if (root1 == NULL && root2 == NULL)
return true;
/* for trees rooted at root1 and root2 to be mirror images,
following conditions must be satisfied */
if (root1 && root2)
/* Their root node's data must be same
if this is not the case then immediately
return false */
return root1->data == root2->data &&
/*left subtree of left tree and right s
ubtree of right tree have to be mirror images*/
utility(root1->left, root2->right) &&
/*right subtree of left tree and left subtree
of right tree have to be mirror images*/
utility(root1->right, root2->left);
/* This condition is reached when :
if only either of root1 or root2 is empty */
return false;
}
/* function to check if tree
rooted at root is Symmetric */
bool isSymmetric(Node* root)
{
// apply utility function to check if tree is mirror of itself
return utility(root, root);
}
// main function to implement above functions
int main()
{
/* construct the binary tree*/
Node *root = new Node(1);
root->left = new Node(2);
root->right = new Node(2);
root->left->left = new Node(3);
root->left->right = new Node(4);
root->right->left = new Node(4);
root->right->right = new Node(3);
isSymmetric(root) ? cout<<"Symmetric Tree" : cout<<"Not Symmetric";
return 0;
}
Symmetric Tree
Program Java dla Symmetric Tree
import java.io.*;
import java.util.*;
class tutorialCup
{
static class Node
{
int data;
Node left;
Node right;
Node(int num)
{
data = num;
left = right = null;
}
};
/*utility function to check whether trees rooted at
root1 and root2 are mirror images of each other or not */
static boolean utility(Node root1, Node root2)
{
/* base case : if both trees are empty then
they are mirror images of each other */
if (root1 == null && root2 == null)
return true;
/* for trees rooted at root1 and root2 to be mirror images,
following conditions must be satisfied */
if (root1 != null && root2 != null)
/* Their root node's data must be same
if this is not the case then immediately
return false */
return root1.data == root2.data &&
/*left subtree of left tree and right s
ubtree of right tree have to be mirror images*/
utility(root1.left, root2.right) &&
/*right subtree of left tree and left subtree
of right tree have to be mirror images*/
utility(root1.right, root2.left);
/* This condition is reached when :
if only either of root1 or root2 is empty */
return false;
}
/* function to check if tree
rooted at root is Symmetric */
static boolean isSymmetric(Node root)
{
// apply utility function to check if tree is mirror of itself
return utility(root, root);
}
/* main function to implement above function */
public static void main (String[] args)
{
/* construct the binary tree*/
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(2);
root.left.left = new Node(3);
root.left.right = new Node(4);
root.right.left = new Node(4);
root.right.right = new Node(3);
if(isSymmetric(root))
System.out.println("Symmetric Tree");
else System.out.println("Not Symmetric");
}
}
Symmetric Tree
Analiza złożoności
- Złożoność czasowa: T (n) = O (n)
- Złożoność przestrzeni: A (n) = O (1) lub O (log n), biorąc pod uwagę przestrzeń stosu rekurencji.
Iteracyjny
Podejście
Chodzi o to, aby przekonwertować podejście rekurencyjne na podejście iteracyjne przy użyciu pliku kolejka strukturę danych, wykonując przeszukiwanie wszerz (BFS)/przechodzenie do kolejności poziomów. Ponownie, używamy 2 kopii drzewa binarnego, powiedzmy b1 i b2 (aby obsługiwać oddzielnie lewe i prawe poddrzewo) i sprawdzamy, czy:
- korzeń wartości b1 i b2 są takie same lub nie.
- lewo poddrzewo b1 i prawo poddrzewo b2 są takie same (zarówno pod względem struktury, jak i wartości węzłów), czy nie.
- prawo poddrzewo b1 i lewo poddrzewo b2 są takie same (zarówno pod względem struktury, jak i wartości węzłów), czy nie.
jeśli warunki 1,2, 3 i XNUMX są prawdziwe Iteracyjnie prawdziwe dla lewego i prawego poddrzewa, po prostu zwracamy prawdę (w przeciwnym razie zwracamy fałsz).
b1 i b2 mają odpowiednio root1 i root2 jako węzeł główny.
Algorytm dla drzewa symetrycznego
- Zdefiniuj przypadki podstawowe.
- Utwórz kolejkę i wepchnij do niej dwie kopie węzła głównego (do obsługi lewego i prawego poddrzewa).
- Rozpocznij przechodzenie BFS i przy każdej iteracji zdejmij dwa węzły z kolejki, a mianowicie leftNode i rightNode.
- jeśli wartość obu węzłów nie jest równa, zwróć false (i zakończ przemierzanie).
- Następnie, jeśli leftNode.left i rightNode.right obie nie mają wartości null, wepchnij je do kolejki.
- jeśli tylko jedno z powyższych nie ma wartości null, zwróci false (i zakończ przemierzanie).
- Następnie, jeśli leftNode.right i rightNode.left nie są zerowe, wepchnij je do kolejki.
- jeśli tylko jedno z powyższych nie jest zerowe, zwraca false (i przerywa przemierzanie).
- Jeśli kolejka stanie się pusta, BFS zostanie zakończony i zwróci wartość true.
1 przykład
2 przykład
Implementacja dla Symmetric Tree
Program C ++ dla drzewa symetrycznego
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
// defining the tree node
class Node
{
public :
int data;
Node *left;
Node *right;
// constructor for initialization
Node(int num)
{
data = num;
left = right = NULL;
}
};
/* function to check if tree
rooted at root is Symmetric */
bool isSymmetric(Node* root)
{
/* base cases */
// 1. if tree is empty it's symmetric
if(root == NULL)
return true;
// 2. if tree has only one node, it's symmetric
if(!root->left && !root->right)
return true;
// create queue for BFS traversal
queue <Node*> q;
/* root is inserted two times so that we can peform
bi-directional BFS to check mirror image property
which is basically a type of bilateral symmetry */
q.push(root);
q.push(root);
/* these store nodes for bi-directional BFS traversal */
Node* leftNode, *rightNode;
while(!q.empty())
{
/* remove nodes to check if they are symmetric or not */
leftNode = q.front();
q.pop();
rightNode = q.front();
q.pop();
/* if both left and right nodes exist but
have different, the tree is not symmetric */
if(leftNode->data != rightNode->data)
return false;
/* Push left child of left subtree node
and right child of right subtree
node in queue */
if(leftNode->left && rightNode->right)
{
q.push(leftNode->left);
q.push(rightNode->right);
}
/* Else if only one child is present alone
and other is NULL, then tree is not symmetric */
else if (leftNode->left || rightNode->right)
return false;
/* Push right child of left subtree node
and left child of right subtree node
in queue */
if(leftNode->right && rightNode->left)
{
q.push(leftNode->right);
q.push(rightNode->left);
}
/* Else if only one child is present alone
and other is NULL, then tree is not symmetric */
else if(leftNode->right || rightNode->left)
return false;
}
/* the tree is symmetric if all the nodes
have been processed and queue becomes empty */
return true;
}
// main function to implement above functions
int main()
{
/* construct the binary tree*/
Node *root = new Node(1);
root->left = new Node(2);
root->right = new Node(2);
root->left->left = new Node(3);
root->left->right = new Node(4);
root->right->left = new Node(4);
root->right->right = new Node(3);
isSymmetric(root) ? cout<<"Symmetric Tree" : cout<<"Not Symmetric";
return 0;
}
Symmetric Tree
Program Java dla Symmetric Tree
import java.io.*;
import java.util.*;
class tutorialCup
{
static class Node
{
int data;
Node left;
Node right;
Node(int num)
{
data = num;
left = right = null;
}
};
/* function to check if tree
rooted at root is Symmetric */
static boolean isSymmetric(Node root)
{
/* base cases */
// 1. if tree is empty it's symmetric
if(root == null)
return true;
// 2. if tree has only one node, it's symmetric
if(root.left == null && root.right == null)
return true;
// create queue for BFS traversal
Queue <Node> q = new LinkedList<>();
/* root is inserted two times so that we can peform
bi-directional BFS to check mirror image property
which is basically a type of bilateral symmetry */
q.add(root);
q.add(root);
/* these store nodes for bi-directional BFS traversal */
Node leftNode, rightNode;
while(!q.isEmpty())
{
/* remove nodes to check if they are symmetric or not */
leftNode = q.poll();
rightNode = q.poll();
/* if both left and right nodes exist but
have different, the tree is not symmetric */
if(leftNode.data != rightNode.data)
return false;
/* Push left child of left subtree node
and right child of right subtree
node in queue */
if(leftNode.left != null && rightNode.right != null)
{
q.add(leftNode.left);
q.add(rightNode.right);
}
/* Else if only one child is present alone
and other is NULL, then tree is not symmetric */
else if (leftNode.left != null || rightNode.right != null)
return false;
/* Push right child of left subtree node
and left child of right subtree node
in queue */
if(leftNode.right != null && rightNode.left != null)
{
q.add(leftNode.right);
q.add(rightNode.left);
}
/* Else if only one child is present alone
and other is NULL, then tree is not symmetric */
else if(leftNode.right != null || rightNode.left != null)
return false;
}
/* the tree is symmetric if all the nodes
have been processed and queue becomes empty */
return true;
}
/* main function to implement above function */
public static void main (String[] args)
{
/* construct the binary tree*/
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(2);
root.left.left = new Node(3);
root.left.right = new Node(4);
root.right.left = new Node(4);
root.right.right = new Node(3);
if(isSymmetric(root))
System.out.println("Symmetric Tree");
else System.out.println("Not Symmetric");
}
}
Symmetric Tree
Analiza złożoności
- Złożoność czasowa: T (n) = O (n)
- Złożoność przestrzeni: A (n) = O (n), używana jest kolejka.
