再谈链表

树

Linked List 就是特殊化的Tree

Tree 就是特殊化的图

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None

public class TreeNode {
    public int val;
    public TreeNode left, right;
    public TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x): val(x), left(NULL), right(NULL) {}
}

二叉搜索树（二叉查找树）

1. 左子树上所有结点的值均小于它的根结点的值；
2. 右子树上所有结点的值均大于它的根结点的值；
3. Recursively，左、右子树也分别为二叉查找树

缺点：退化 -- > 链表

红黑树 Red-Black Tree（Java标准库）

Splay Tree

AVL Tree

KD Tree

图

题目练习

验证二叉搜索树

方法一：In-order --> array 查看是否是升序 O(n)

方法二：Recursion: validate(..., min, max) O(n)

Max <-- validate(node.left)

Min <-- valadate(node.rigtht)

Max<root ， min >root

def isValidBST(self, root):
    inorder = self.inorder(root)
    return inorder == list(sorted(set(inorder)))
  
def inorder(self, root):
    if root is None:
        return []
    return self.inorder(root.left) + [root.val] + self.inorder(root.right)

def isValidBST(self, root):
    self.prev = None
    return self.helper(root)
  
def helper(self, root):
    if root is None:
        return True
    if not self.helper(root.left):
        return False
    if self.prev and self.prev.val >= root >= root.val:
        return False
    self.prev = root
    return self.helper(root.right)

public boolean isValid(TreeNode root, Integer min, Integer max) {
    if(root == null) return true;
    if(min != null && root.val <= min) return false;
    if(max != null && root.val >= max) return false;
  
    return isValid(root.left, min, root.val) && isValid(root.right, root.val, max);
}