平衡二叉樹


難度級別 容易獎學金
經常問 亞馬遜 彭博社 谷歌 Microsoft微軟
二叉樹 深度優先搜索 遞歸

在平衡二叉樹問題中,我們給出了a的根 二叉樹。 我們必須確定它是否是高度平衡。

範例檔案

輸入

平衡二叉樹

產量

輸入

平衡二叉樹

輸出:

平衡二叉樹

平衡二進制中的每個節點 左右子樹的高度相差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

平衡二叉樹的優化方法

如果滿足樹的高度平衡屬性,則修改height函數以返回樹的高度,否則返回-1。

  1. 空樹始終遵循高度平衡(基本情況)。
  2. 通過遞歸調用height函數來找到左側的高度,如果height為-1,則左子樹不平衡,請立即返回-1。
  3. 通過遞歸調用height函數來找到合適的高度,如果height為-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

參考