二叉树相关算法题

如果中序遍历为有序的话则为二叉搜索树，为了避免退化为单链表，加入平衡规则后保持平衡则为平衡二叉树，搜索的时间复杂度为O(lgn).
满二叉树、完全二叉树又推出最大堆、最小堆（堆排序、定时器）。平衡二叉树又推出avl、红黑树。
对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

二叉树的递归遍历

前序遍历：根->左->右，1>2>4>5>3>6>7，245这棵树是作为一个整体子树从根节点遍历，这就是递归的思想。
中序遍历：左->根->右，4>2>5>1>6>3>7，每次遍历到子树也是重新左->根->右进行遍历。
后序遍历：左->右->根，4>5>2>6>7>3>1

void PreOrder(TreeNode *root)
{
    if (root == nullptr) return;
    result.push_back(root->val);
    PreOrder(root->left);
    PreOrder(root->right);
}

void InOrder(TreeNode *root)
{
    if (root == nullptr) return;
    InOrder(root->left);
    result.push_back(root->val);
    InOrder(root->right);
}

void PostOrder(TreeNode *root)
{
    if (root == nullptr) return;
    PostOrder(root->left);
    PostOrder(root->right);
    result.push_back(root->val);
}

二叉树的迭代遍历

栈是先进后出，前序遍历：根->左->右，1>2>4>5>3>6>7，所以要从右边往左进行压栈，顺序为右->左->根，思维方式恰好相反。

void PreOrder(TreeNode *root)
{
    if (root == nullptr) return;
    stack<TreeNode*> st;
    st.push(root); // 先入根节点
    while (!st.empty()) {
        // 右->左->根
        TreeNode* node = st.top(); st.pop();
        if (node != nullptr) {
            if (node->right != nullptr) st.push(node->right);
            if (node->left != nullptr) st.push(node->left);
            st.push(node);
            st.push(nullptr); // 标记后面就是根节点
        } else { // 遇到标记才打印根节点
            node = st.top(); st.pop();
            result.push_back(node->val);
        }
    }
}

void InOrder(TreeNode *root)
{
    if (root == nullptr) return;
    stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        // 右->根->左
        TreeNode* node = st.top(); st.pop();
        if (node != nullptr) {
            if (node->right != nullptr) st.push(node->right);
            st.push(node);
            st.push(nullptr); // 标记后面就是根节点
            if (node->left != nullptr) st.push(node->left);
        } else { // 遇到标记才打印根节点
            node = st.top(); st.pop();
            result.push_back(node->val);
        }
    }
}

void PostOrder(TreeNode *root)
{
    if (root == nullptr) return;
    stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        // 根->右->左
        TreeNode* node = st.top(); st.pop();
        if (node != nullptr) {
            st.push(node);
            st.push(nullptr); // 标记后面就是根节点
            if (node->right != nullptr) st.push(node->right);
            if (node->left != nullptr) st.push(node->left);
        } else { // 遇到标记才打印根节点
            node = st.top(); st.pop();
            result.push_back(node->val);
        }
    }
}

二叉树的层序遍历

广度优先搜索，需要使用队列来实现，和迭代类似，也是要让根节点先入，根节点弹出队列前，要把左右子节点入队列。

vector<int> traverse(TreeNode *root)
{
    vector<int> result;
    if (root == nullptr) return result;
    queue<TreeNode*> que;
    que.push(root);
    while (!que.empty()) {
        size_t size = que.size();
        for (size_t i = 0; i < size; i++) { // 这里可以不写，但要知道它的存在
            TreeNode *node = que.front(); que.pop();
            result.push_back(node->val);
            if (node->left != nullptr) que.push(node->left); // 取出来后要将左右节点放进去
            if (node->right != nullptr) que.push(node->right);
        }
    }
}

// 按层打印
vector<vector<int>> traverse(TreeNode *root)
{
    vector<vector<int>> result;
    if (root == nullptr) return result;
    queue<TreeNode*> que;
    que.push(root);
    while (!que.empty()) {
        size_t size = que.size();
        vector<int> res;
        for (size_t i = 0; i < size; i++) { // 记录这一层有多少个节点
            TreeNode *node = que.front(); que.pop();
            res.push_back(node->val);
            if (node->left != nullptr) que.push(node->left); // 取出来后要将左右节点放进去
            if (node->right != nullptr) que.push(node->right);
        }
        result.push_back(res);
    }
}

二叉树树形dp

求最优解问题、且子问题的解有重叠（某个节点的解是其父节点的一部分），需要找到状态转移方程。
从二叉树的节点A出发，可以向上或向下走，但沿途的节点只能经过一次，当达到节点B时，路径上的节点树叫做A到B到距离。

这棵树的最大距离（首先构建出这个模型，和高中的受力分析意义画出图来）：max(左子树的最大距离，右子树的最大距离，左子树的高度+右子树的高度+1)
子问题的解有重叠：f(n-1)是f(n)解的一部分，确定边界值为某个叶子节点的解为f(0)=max(0, 0, 1)=1。

struct RetVal { // 涉及到两个变量，先定义结构体
    int distance;
    int height;
    RetVal(int dis, int hgt) : distance(dis), height(hgt) {}
};

int Do(TreeNode *root)
{
    if (root == nullptr) return 0;
    return dfs(root).distance;
}

// 后序遍历
RetVal dfs(TreeNode *root)
{
    if (root == nullptr) return RetVal(0, 0);
    RetVal left = dfs(root->left);
    RetVal right = dfs(root->right);
    int height = std::max(left.height, right.height) + 1; // 需要计算高度
    // 左子树的最大距离，右子树的最大距离，左子树的高度+右子树的高度+1
    return RetVal(std::max(std::max(left.distance, right.distance), left.height + right.height + 1), height);
}