树

树是非线性的存储结构，存储的是“一对多”的数据元素集合。
在代码实现上，一般使用单独的类作为一个树节点，如：

// 二叉树结构
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

属性术语

节点

所谓节点指的是包含 TreeNode 结构的数据元素，图中所有数据元素都是一个节点

根节点

图中 节点A 为整棵树的根节点，在编码实现上，我们一般保存的是根节点的指针，通过根节点可以到达其余所有节点

父节点

当某个节点之下还有其他节点时，称为父节点，比如 节点A、B

子节点

当某个节点之上有其他节点时，称为子节点，比如 节点B、C、D 以及 节点E、F

兄弟节点

当某个节点有相同的父节点时，称为兄弟节点，比如 节点B、C、D 以及 节点E、F

堂兄弟节点

处于同一层的节点都是堂兄弟节点

节点的祖先

从根节点到该节点所经过的节点都是该节点的祖先节点，有些算法会有计算相同祖先节点的要求

子孙节点

以某个节点为根节点之下的所有节点都是该节点的子孙节点

叶子节点

当某个节点没有任何子节点时，称为叶子节点，比如 节点E、F 以及 节点C、D

子树

指的是根节点以下形成的数结构，比如 节点B、E、F 就是一颗子树

空树

指的是没有任何节点

森林

用以描述m（m>=0）棵互不相交的树的集合

度

节点的度指的是节点有多少个子树，比如 节点A的度为3，节点B的度为2，节点C的度为0，而树的度指的是最大节点度。因此叶子节点的度为0

树的层次

根节点为第一层，根的子节点为第二层，以此类推。因此第一层有：节点A，第二层有：节点B、C、D，第三层有：节点E、F

树的高度

从下往上计算，叶子节点的高度为0，某个节点的高度指的是从该节点到叶子节点的最长路径，树的高度指的是根节点到叶子节点的最长路径

树的深度

从上往下计算，根节点的深度为0，树的深度指的是根节点到叶子节点的最长路径，因此实际上 高度 = 深度

树的种类

二叉树

每个节点最多包含两个子树

完全二叉树

对于一个二叉树来说，除了最底的层，其余层的节点数都达到最大值，且最底层的所有节点从左到右连续紧密排列

（注：节点的值没有大小关系）

满二叉树

在完全二叉树的基础上，在最底层的节点数也是满的，则为满二叉树

（注：节点的值没有大小关系）

二叉搜索树（BST，Binary Search Tree）

任意一个节点的所有左子树存储的数据都 小于或等于 节点自身存储的数据，右子树存储的数据都 大于或等于 节点自身存储的数据

查找

查找的平均时间复杂度为 O(logn)，n是树的高度。当二叉搜索树不平衡时，如退化成了链表，则时间复杂度是O(n)。

查找的过程是：判断当前节点（初始时是根节点）与目标值的大小关系，如果目标值大于当前节点，则更新当前节点为原节点的右子节点，继续搜索。如果目标值小于当前节点，则更新当前节点为原节点的左子节点，继续搜索。在搜索过程中如果遇到空节点，则代表目标值不在树种，否则必定能查找到目标节点

插入

插入的流程与查找流程相似，依然通过逐个比较当前节点与目标值的差别，最终找到空槽位并插入
下图演示的是插入 节点2、5、11 的位置

相同节点但是不同的插入顺序会导致不一样的树结构，在不进行结构优化的情况下，可能就会使树退化成链表结构

平衡二叉树（AVL）

当且仅当任意节点的两棵子树的高度差不大于1的二叉树，本质是为了避免二叉搜索树的退化

当有 节点H 时，对于节点B来说，左子树的高为2，右子树为0，就不符合定义了。
（注：节点的值没有大小关系）

插入和删除

相比较于二叉搜索树的直接插入和删除，需要进行结构调整，分为 单左旋、单右旋、双左旋、双右旋 四种，以形成新的平衡二叉树

红黑树（RB-Tree）

当使用AVL树时，每次的插入删除基本上都会触发重平衡，是一种绝对平衡，因此性能较低。
而红黑树则是一种相对的平衡，满足以下特性：

1. 每个节点都是黑色或者红色
2. 根节点时黑色
3. 每个叶子节点都是黑色的 （注意这里指的是NULL节点）
4. 如果一个节点是红色的，那么它的子节点必须是黑色的
5. 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点
   这样确保从根结点到叶子节点的最长路径不大于最短路径的 2 倍。由纯黑节点组成的路径必定是最短路径（因为红节点之后必有两个黑色的子节点），因此在原有最短路径的黑色节点之间插入红色节点，即可得到相同数目的黑色节点下的最长路径，且该长度不超过最短路径的 2 倍。
6. 新加入的节点是红色节点

插入和删除

需要经过 旋转和变色 以重平衡红黑树

树的遍历

前序遍历

// 递归方式
class Solution {
    public:
    vector<int> res;
    vector<int> preorderTraversal(TreeNode* root) {
        if (root == nullptr)
        {
            return res;
        }
        res.push_back(root->val);
        preorderTraversal(root->left);
        preorderTraversal(root->right);
        return res;
    }
};

// 迭代方式
class Solution {
    public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> myStack;
        vector<int> res;
        while (!myStack.empty() || root != nullptr)
        {
            while (root != nullptr)
            {
                res.push_back(root->val);
                myStack.push(root);
                root = root->left;
            }
            root = myStack.top();
            myStack.pop();
            root = root->right;
        }
        return res;
    }
};

中序遍历

// 递归方式
class Solution {
    public:
    vector<int> res;
    vector<int> inorderTraversal(TreeNode* root) {
        if (!root)
        {
            return res;
        }
        inorderTraversal(root->left);
        res.push_back(root->val);
        inorderTraversal(root->right);
        return res;
    }
};

// 迭代方式
class Solution {
    public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> myStack;
        while (!myStack.empty() || root != nullptr)
        {
            while (root != nullptr)
            {
                myStack.push(root);
                root = root->left;
            }
            root = myStack.top();
            res.push_back(root->val);
            myStack.pop();
            root = root->right;
        }
        return res;
    }
};

后序遍历

// 递归方式
class Solution {
    public:
    vector<int> res;
    vector<int> postorderTraversal(TreeNode* root) {
        if (root == nullptr)
        {
            return res;
        }
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        res.push_back(root->val);
        return res;
    }
};

// 迭代方式
class Solution {
    public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> myStack;
        vector<int> res;
        TreeNode* pre = nullptr;
        while (!myStack.empty() || root != nullptr)
        {
            while (root != nullptr)
            {
                myStack.push(root);
                root = root->left;
            }
            root = myStack.top(); // root 有可能是左子节点，也可能是某个根节点
            if (!root->right || root->right == pre) // pre记载的上一个节点，防止root又计算到另外的right
            {
                res.push_back(root->val);
                myStack.pop();
                pre = root;
                root = nullptr;
            }
            else // 如果这个节点有右子节点
            {
                root = root->right;
            }
        }
        return res;
    }
};

层次遍历

class Solution {
    public:
    vector<int> layerTraversal(TreeNode* root) {
        vector<int> res;
        queue<TreeNode*> myQue; // 使用优先队列
        myQue.push(root);
        while (!myQue.empty())
        {
            int n = myQue.size();
            for (int i = 0; i < n; ++i)
            {
                root = myQue.front();
                myQue.pop();
                res.push_back(root->val);
                if (root->left != nullptr)
                {
                    myQue.push(root->left);
                }
                if (root->right != nullptr)
                {
                    myQue.push(root->right);
                }
            }
        }
        return res;
    }
};