What is the best way to solve AVL Tree?

The optimized O(n) approach using Trees patterns is generally preferred.

DSA 部分中等

AVL樹

“AVL 樹”問題的詳細指南和 Python 實作。

問題陳述

中等

寫一個函數 is_avl_balanced(tree_arr) ，它採用二元樹 tree_arr 的陣列表示形式，如果樹是高度平衡的（對於每個節點，其左右子樹的高度最多相差 1）並且是有效的 BST，則傳回 True ，否則傳回 False 。

約束條件

•0 <= len(tree_arr) <= 1000

範例

Example 1

Input

tree_arr = [3, 9, 20, None, None, 15, 7]

Output

True

Explanation

The tree is a valid BST and the depth difference of left/right subtrees of all nodes is at most 1.

Example 2

Input

tree_arr = [1, 2, None, 3, None, None, None, 4]

Output

False

Explanation

The tree is unbalanced because leaf node 4 is at depth 4 while right subtree of node 1 is empty.

Need a Hint?

考慮使用樹特定的資料結構，例如集合或堆。

Edge Cases to Watch

空輸入結構
單元素輸入
大數值範圍

準備好解決了嗎？

Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.

在編輯器中開啟

面試見解和變化

解釋你的樹方法的邏輯。

討論諸如 null 或空輸入之類的邊緣情況。

複雜度分析分解

蠻力複雜性

Time: O(n)•Space: O(1)

為什麼時間: Directly evaluates all possibilities.

為什麼選擇太空: Uses standard local memory.

優化的複雜性

Time: O(n)•Space: O(n)

為什麼時間: Optimized paths reduce total operations.

為什麼選擇太空: May trade memory for speed.

最佳化解決方案Python程式碼

在編譯器中嘗試

def create_avl_tree_opt(arr: list) -> list:
    class AVLTreeNode:
        def __init__(self, val=0):
            self.val = val
            self.left = None
            self.right = None
            self.height = 1
            
    def get_height(node):
        return node.height if node else 0
        
    def get_balance(node):
        return get_height(node.left) - get_height(node.right) if node else 0
        
    def rotate_right(y):
        x = y.left
        T2 = x.right
        x.right = y
        y.left = T2
        y.height = 1 + max(get_height(y.left), get_height(y.right))
        x.height = 1 + max(get_height(x.left), get_height(x.right))
        return x
        
    def rotate_left(x):
        y = x.right
        T2 = y.left
        y.left = x
        x.right = T2
        x.height = 1 + max(get_height(x.left), get_height(x.right))
        y.height = 1 + max(get_height(y.left), get_height(y.right))
        return y
        
    def insert(node, val):
        if not node:
            return AVLTreeNode(val)
        if val < node.val:
            node.left = insert(node.left, val)
        else:
            node.right = insert(node.right, val)
            
        node.height = 1 + max(get_height(node.left), get_height(node.right))
        balance = get_balance(node)
        
        # Left Left
        if balance > 1 and val < node.left.val:
            return rotate_right(node)
        # Right Right
        if balance < -1 and val > node.right.val:
            return rotate_left(node)
        # Left Right
        if balance > 1 and val > node.left.val:
            node.left = rotate_left(node.left)
            return rotate_right(node)
        # Right Left
        if balance < -1 and val < node.right.val:
            node.right = rotate_right(node.right)
            return rotate_left(node)
            
        return node
        
    if not arr: return []
    root = None
    for val in arr:
        root = insert(root, val)
        
    # Serialize level-order
    res = []
    queue = [root]
    while queue:
        curr = queue.pop(0)
        if curr:
            res.append(curr.val)
            queue.append(curr.left)
            queue.append(curr.right)
        else:
            res.append(None)
    while res and res[-1] is None:
        res.pop()
    return res

暴力破解代碼（劇透保護）

在編譯器中嘗試

def create_avl_tree_brute(arr: list) -> list:
    # Standard AVL tree insertion with rotations, returns level order list
    class AVLTreeNode:
        def __init__(self, val=0):
            self.val = val
            self.left = None
            self.right = None
            self.height = 1
            
    def get_height(node):
        return node.height if node else 0
        
    def get_balance(node):
        return get_height(node.left) - get_height(node.right) if node else 0
        
    def rotate_right(y):
        x = y.left
        T2 = x.right
        x.right = y
        y.left = T2
        y.height = 1 + max(get_height(y.left), get_height(y.right))
        x.height = 1 + max(get_height(x.left), get_height(x.right))
        return x
        
    def rotate_left(x):
        y = x.right
        T2 = y.left
        y.left = x
        x.right = T2
        x.height = 1 + max(get_height(x.left), get_height(x.right))
        y.height = 1 + max(get_height(y.left), get_height(y.right))
        return y
        
    def insert(node, val):
        if not node:
            return AVLTreeNode(val)
        if val < node.val:
            node.left = insert(node.left, val)
        else:
            node.right = insert(node.right, val)
            
        node.height = 1 + max(get_height(node.left), get_height(node.right))
        balance = get_balance(node)
        
        if balance > 1 and val < node.left.val:
            return rotate_right(node)
        if balance < -1 and val > node.right.val:
            return rotate_left(node)
        if balance > 1 and val > node.left.val:
            node.left = rotate_left(node.left)
            return rotate_right(node)
        if balance < -1 and val < node.right.val:
            node.right = rotate_right(node.right)
            return rotate_left(node)
        return node
        
    if not arr: return []
    root = None
    for val in arr:
        root = insert(root, val)
    return tree_to_list(root)

☕Found this breakdown helpful?

PyRun is built and maintained by an independent solo developer. If this helped your interview prep, consider buying a coffee!

☕Buy me a coffee

AVL樹

1. 學習

2. Real-World Applications

3. Visual Intuition

4. Prerequisites

5. Step-by-Step Thinking

1. Understand the problem

2. Formulate brute force

3. Identify inefficiency

4. Optimize search path

5. Final Implementation

問題陳述

範例

準備好解決了嗎？

面試見解和變化

複雜度分析分解

最佳化解決方案Python程式碼

暴力破解代碼（劇透保護）

Algorithm Pattern Checklist

Key Revision Notes

相關問題

推薦的 Python 資源

Python 迴圈：For 與 While 迴圈解釋

如何在 Python 中對列表進行排序（升序和降序）

Python 字串方法備忘單

Python 與 JavaScript：哪種程式語言最好？