二叉树相关算法题

发表于 2021-02-13 更新于 2025-06-08 Changyan：

如果中序遍历为有序的话则为二叉搜索树，为了避免退化为单链表，加入平衡规则后保持平衡则为平衡二叉树，搜索的时间复杂度为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);
}

翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

根据二叉树镜像的定义，考虑递归遍历（dfs）二叉树，交换每个节点的左 / 右子节点，即可生成二叉树的镜像。
Q：为何需要暂存 root 的左子节点？
A：在递归右子节点 “root.left=invertTree(root.right);” 执行完毕后， root.left 的值已经发生改变，此时递归左子节点 invertTree(root.left) 则会出问题。

TreeNode* invertTree(TreeNode* root) {
    if (root == nullptr) return nullptr;
    TreeNode* tmp = root->left;
    root->left = invertTree(root->right);
    root->right = invertTree(tmp);
    return root;
}

利用栈（或队列）遍历树的所有节点 nodenodenode ，并交换每个 nodenodenode 的左 / 右子节点。

TreeNode* invertTree(TreeNode* root) {
    if (root == nullptr) return nullptr;
    stack<TreeNode*> stack;
    stack.push(root);
    while (!stack.empty())
    {
        TreeNode* node = stack.top();
        stack.pop();
        if (node->left != nullptr) stack.push(node->left);
        if (node->right != nullptr) stack.push(node->right);
        TreeNode* tmp = node->left;
        node->left = node->right;
        node->right = tmp;
    }
    return root;
}

二叉搜索树中的插入操作

给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。你可以返回任意有效的结果。

根据二叉搜索树的性质，可以巧妙的将待插入结点转变为叶子结点插入，从而避免改变二叉树原有整体结构。原因：二叉树搜索树本身就是有序的，按照其有序性，遍历找到目标val位置，一定能找到空子树，即NULL，此时构建新节点，将val插入即可。

// 递归
TreeNode* insertIntoBST(TreeNode* root, int val) {
    if(root == NULL) return new TreeNode(val);
    if(root->val > val) root->left = insertIntoBST(root->left, val);
    else root->right = insertIntoBST(root->right, val);
    return root;
}
// 迭代
TreeNode* insertIntoBST(TreeNode* root, int val) {
    if(root == NULL) return new TreeNode(val);
    TreeNode* cur = root;
    while (cur != NULL) {
        if (cur->val > val){
            if (cur->left == NULL){ 
                cur->left = new TreeNode(val);
                break;
            } else {
                cur = cur->left;
            }
        } else {
            if (cur->right == NULL) {
                cur->right = new TreeNode(val);
                break;
            } else {
                cur = cur->right;
            }
        }
    }
    return root;
}

二叉树最大深度？

给定一个二叉树 root ，返回其最大深度。
二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。
思路：
使用两个栈，一个用于存储节点，另一个用于存储节点的深度。我们从根节点开始，逐层遍历树的节点，同时记录每个节点的深度。最终，返回最大深度作为结果。这种方法避免了递归，减小了函数调用栈的开销。

int maxDepth(TreeNode* root) {
    if (root == nullptr) {
        return 0;  // 如果根节点为空，返回深度0
    }

    // 使用DFS进行深度搜索
    std::stack<TreeNode*> nodes;
    std::stack<int> depths;
    int max = 0;

    nodes.push(root);
    depths.push(1);  // 根节点的深度为1

    while (!nodes.empty()) {
        TreeNode* node = nodes.top();
        nodes.pop();
        int depth = depths.top();
        depths.pop();
        max = std::max(max, depth);  // 更新最大深度

        // 遍历左子树
        if (node->left) {
            nodes.push(node->left);
            depths.push(depth + 1);  // 左子树深度加1
        }
        // 遍历右子树
        if (node->right) {
            nodes.push(node->right);
            depths.push(depth + 1);  // 右子树深度加1
        }
    }

    return max;  // 返回最大深度
}