균형 이진 트리

난이도 쉽게
자주 묻는 질문 아마존 블룸버그 게시물에서 구글 Microsoft
이진 트리 깊이 우선 검색 재귀 나무조회수 78

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

균형 이진 트리 문제에서 우리는 이진 트리. 높이 균형인지 아닌지를 결정해야합니다.

입력

균형 이진 트리

산출

참된

입력

균형 이진 트리

출력:

그릇된

균형 이진 트리

균형 잡힌 바이너리의 모든 노드 나무 왼쪽 및 오른쪽 하위 트리 높이의 차이가 1 이하입니다. 빈 나무는 항상 높이 균형을 따릅니다.
즉, 균형 잡힌 이진 트리의 경우
-1 <= 왼쪽 하위 트리의 높이 – 오른쪽 하위 트리의 높이 <= 1

균형 이진 트리에 대한 순진한 접근 방식

모든 노드가 왼쪽 및 오른쪽 하위 트리의 높이를 계산하려면 차이가 1보다 크면 false를 반환하고 그렇지 않으면 왼쪽과 오른쪽 하위 트리에 대해 반복하고 둘 다 균형이 맞으면 true를 반환하고 다른 모든 경우에는 false를 반환합니다.
기본 케이스: 빈 나무는 높이 균형을 따릅니다.

  1. 루트에서 시작하십시오. 루트가 null이면 true를 반환합니다.
  2. 왼쪽 및 오른쪽 하위 트리의 높이를 계산하고 각각 leftHeight 및 rightHeight라는 변수에 저장합니다.
  3. 루트의 왼쪽 및 오른쪽 하위 트리에 대해 균형 높이 함수를 재귀 적으로 호출합니다. 왼쪽 및 오른쪽 하위 트리가 모두 균형을 이루고 leftHeight와 rightHeight의 차이가 1보다 작거나 같으면 true를 반환하고 그렇지 않으면 false를 반환합니다.

시간 복잡성 = O (n ^ 2)

JAVA 코드

public class BalancedBinaryTree {
    static class Node {
        int data;
        Node left;
        Node right;

        public Node(int data) {
            this.data = data;
            left = right = null;
        }
    }

    // Function to calculate height of a tree rooted at root
    private static int height(Node root) {
        if (root == null) {
            // Height of empty tree is 0
            return 0;
        }
        // Height of tree is 1 + maximum of height of left or right subtree
        return 1 + Math.max(height(root.left), height(root.right));
    }

    // Function to check if given tree is balanced or not
    private static boolean isBalanced(Node root) {
        if (root == null) {
            // Empty tree is always balanced
            return true;
        }

        // Find the left subtree height and right subtree height
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);

        // If this node is balanced and also its left and right subtree are balanced return true
        // else return false
        return (Math.abs(leftHeight - rightHeight) <= 1) && isBalanced(root.left)
                && isBalanced(root.right);
    }

    public static void main(String[] args) {
        // Tree in example 1
        Node root = new Node(18);
        root.left = new Node(4);
        root.right = new Node(20);
        root.right.left = new Node(13);
        root.right.right = new Node(70);

        System.out.println(isBalanced(root));

        // Tree in example 2
        Node root2 = new Node(3);
        root2.left = new Node(4);
        root2.right = new Node(8);
        root2.left.left = new Node(5);
        root2.left.right = new Node(9);
        root2.right.right = new Node(7);
        root2.right.right.left = new Node(6);

        System.out.println(isBalanced(root2));
    }
}

C ++ 코드

#include <iostream>
using namespace std;

class Node {
    public:
    int data;
    Node *left;
    Node *right;
};

// Function to calculate height of a tree rooted at root
int height(Node *root) {
    if (root == NULL) {
        // Height of empty tree is 0
        return 0;
    }
    // Height of tree is 1 + maximum of height of left or right subtree
    return 1 + std::max(height(root->left), height(root->right));
}

// Function to check if given tree is balanced or not
bool isBalanced(Node *root) {
    if (root == NULL) {
        // Empty tree is always balanced
        return true;
    }

    // Find the left subtree height and right subtree height
    int leftHeight = height(root->left);
    int rightHeight = height(root->right);

    // If this node is balanced and also its left and right subtree are alanced return true
    // else return false
    return (abs(leftHeight - rightHeight) <= 1) && isBalanced(root->left)
            && isBalanced(root->right);
}

// Function to allocate new memory to a tree node
Node* newNode(int data) { 
    Node *node = new Node(); 
    node->data = data; 
    node->left = NULL; 
    node->right = NULL;
  
    return (node); 
}

int main() {
  // Tree in example 1
    Node *root = newNode(18);
    root->left = newNode(4);
    root->right = newNode(20);
    root->right->left = newNode(13);
    root->right->right = newNode(70);

    if (isBalanced(root) == true) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Tree in example 2
    Node* root2 = newNode(3);
    root2->left = newNode(4);
    root2->right = newNode(8);
    root2->left->left = newNode(5);
    root2->left->right = newNode(9);
    root2->right->right = newNode(7);
    root2->right->right->left = newNode(6);

    if (isBalanced(root2) == true) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    return 0;
}
true
false

균형 이진 트리를위한 최적화 된 접근 방식

나무가 높이 균형 속성을 만족하면 나무의 높이를 반환하도록 높이 함수를 수정하고 그렇지 않으면 -1을 반환합니다.

  1. 빈 트리는 항상 높이 균형 (Base Case)을 따릅니다.
  2. height 함수를 재귀 적으로 호출하여 왼쪽 높이를 찾으십시오. 높이가 -1이면 왼쪽 하위 트리가 균형이 맞지 않으면 즉시 -1을 반환합니다.
  3. 높이 함수를 재귀 적으로 호출하여 올바른 높이를 찾으십시오. 높이가 -1이면 오른쪽 하위 트리가 불균형 상태가되고 즉시 -1을 반환합니다.
  4. 왼쪽과 오른쪽 높이의 차이가 1보다 작거나 같으면 height (1 + max (leftHeight, rightHeight))를 반환하고 그렇지 않으면 -1을 반환합니다.

시간 복잡성 = O (N)

JAVA 코드

public class BalancedBinaryTree {
    static class Node {
        int data;
        Node left;
        Node right;

        public Node(int data) {
            this.data = data;
            left = right = null;
        }
    }

    // Modified height function
    // Returns the height of tree if the tree is balanced and returns -1 is the tree is not balanced
    private static int height(Node root) {
        if (root == null) {
            // Empty tree is always balanced
            return 0;
        }

        // Find the left height
        int lh = height(root.left);
        if (lh == -1) {
            // Left subtree is unbalanced
            return -1;
        }
        // Find the right height
        int rh = height(root.right);
        if (rh == -1) {
            // Right subtree is unbalanced
            return -1;
        }
        if (Math.abs(lh - rh) <= 1) {
            // Balanced tree, return the height
            return Math.max(lh, rh) + 1;
        }
        // Unbalanced tree
        return -1;
    }

    private static boolean isBalanced(Node root) {
        // Call the modified height function
        int height = height(root);
        if (height == -1) {
            // Unbalanced tree
            return false;
        }
        // Balanced tree
        return true;
    }

    public static void main(String[] args) {
        // Tree in example 1
        Node root = new Node(18);
        root.left = new Node(4);
        root.right = new Node(20);
        root.right.left = new Node(13);
        root.right.right = new Node(70);

        System.out.println(isBalanced(root));

        // Tree in example 2
        Node root2 = new Node(3);
        root2.left = new Node(4);
        root2.right = new Node(8);
        root2.left.left = new Node(5);
        root2.left.right = new Node(9);
        root2.right.right = new Node(7);
        root2.right.right.left = new Node(6);

        System.out.println(isBalanced(root2));
    }
}

C ++ 코드

#include <iostream>
using namespace std;

class Node {
    public:
    int data;
    Node *left;
    Node *right;
};

// Function to calculate height of a tree rooted at root
int height(Node *root) {
    if (root == NULL) {
        // Empty tree is always balanced
        return 0;
    }
    // Find the left height
    int lh = height(root->left);
    if (lh == -1) {
        // Left subtree is unbalanced
        return -1;
    }
    // Find the right height
    int rh = height(root->right);
    if (rh == -1) {
        // Right subtree is unbalanced
        return -1;
    }
    if (abs(lh - rh) <= 1) {
        // Balanced tree, return the height
        return 1 + std::max(height(root->left), height(root->right));
    }
    // Unbalanced tree
    return -1;
}

// Function to check if given tree is balanced or not
bool isBalanced(Node *root) {
    // Call the modified height function
    int h = height(root);
    if (h == -1) {
        // Unbalanced tree
        return false;
    }
    // Balanced tree
    return true;
}

// Function to allocate new memory to a tree node
Node* newNode(int data) { 
    Node *node = new Node(); 
    node->data = data; 
    node->left = NULL; 
    node->right = NULL;
  
    return (node); 
}

int main() {
  // Tree in example 1
    Node *root = newNode(18);
    root->left = newNode(4);
    root->right = newNode(20);
    root->right->left = newNode(13);
    root->right->right = newNode(70);

    if (isBalanced(root) == true) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Tree in example 2
    Node* root2 = newNode(3);
    root2->left = newNode(4);
    root2->right = newNode(8);
    root2->left->left = newNode(5);
    root2->left->right = newNode(9);
    root2->right->right = newNode(7);
    root2->right->right->left = newNode(6);

    if (isBalanced(root2) == true) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    return 0;
}
true
false

참조

균열 시스템 설계 인터뷰
Translate »