[数据结构与算法] LeetCode常见题型—

1. 算法思想

作为（单）链表的升级版，我们通常接触的树都是二叉树（binary tree），即每个节点最多有
两个子节点；且除非题目说明，默认树中不存在循环结构。

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

2.常见题型

2.1 树的递归

对于一些简单的递归题，某些LeetCode 达人喜欢写one-line code，即用一行代码解决问题，
把if-else 判断语句压缩成问号冒号的形式。

2.2 层次遍历

注意，不需要使用两个队列来分别存储当前层的节点和下一层的节点，因为在开始遍历一层的节点时，当前队列中的节点数就是当前层的节点数，只要控制遍历这么多节点数，就能保证这次遍历的都是当前层的节点。

2.3 前中后序遍历

2.4?二叉查找树

二叉查找树（Binary Search Tree, BST）是一种特殊的二叉树：对于每个父节点，其左子节点
的值小于等于父结点的值，其右子节点的值大于等于父结点的值。因此对于一个二叉查找树，我
们可以在O(nlogn)?的时间内查找一个值是否存在：从根节点开始，若当前节点的值大于查找值
则向左下走，若当前节点的值小于查找值则向右下走。同时因为二叉查找树是有序的，对其中序
遍历的结果即为排好序的数组。

template <class T>
class BST {
    struct Node {
        T data;
        Node* left;
        Node* right;
    };
    Node* root;
    
    Node* makeEmpty(Node* t) {
        if (t == NULL) return NULL;
        makeEmpty(t->left);
        makeEmpty(t->right);
        delete t;
        return NULL;
    }
    
    Node* insert(Node* t, T x) {
        if (t == NULL) {
            t = new Node;
            t->data = x;
            t->left = t->right = NULL;
        } else if (x < t->data) {
            t->left = insert(t->left, x);
        } else if (x > t->data) {
            t->right = insert(t->right, x);
        }
        return t;
    }
    
    Node* find(Node* t, T x) {
        if (t == NULL) return NULL;
        if (x < t->data) return find(t->left, x);
        if (x > t->data) return find(t->right, x);
        return t;
    }
    
    Node* findMin(Node* t) {
        if (t == NULL || t->left == NULL) return t;
            return findMin(t->left);
        }
        Node* findMax(Node* t) {
        if (t == NULL || t->right == NULL) return t;
        return findMax(t->right);
    }
    
    Node* remove(Node* t, T x) {
        Node* temp;
        if (t == NULL) return NULL;
        else if (x < t->data) t->left = remove(t->left, x);
        else if (x > t->data) t->right = remove(t->right, x);
        else if (t->left && t->right) {
            temp = findMin(t->right);
            t->data = temp->data;
            t->right = remove(t->right, t->data);
        } else {
            temp = t;
            if (t->left == NULL) t = t->right;
            else if (t->right == NULL) t = t->left;
            delete temp;
        }
        return t;
    }

public:
    BST(): root(NULL) {}
    ~BST() {
        root = makeEmpty(root);
    }
    void insert(T x) {
        insert(root, x);
    }
    void remove(T x) {
        remove(root, x);
    }
};

2.5 字典树

字典树（Trie）用于判断字符串是否存在或者是否具有某种字符串前缀。

可以在O(n)——近似O(1)的时间内完成搜索，且额外开销非常小。