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：哪种编程语言最好？