AI 助理
备案控制台
开发者社区 人工智能 文章 正文

二叉树常见OJ题（笔记）

2023-07-20 230
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 本篇总结了常见二叉树算法题，每个标题都有超链接，并给出AC代码。记得以后再刷几遍，容易忘记。

前言

本篇总结了常见二叉树算法题，每个标题都有超链接，并给出AC代码。记得以后再刷几遍，容易忘记。

1. 根据二叉树创建字符串

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    string tree2str(TreeNode* root) {
        if(root==nullptr)
            return string();
        string str;
        str+=to_string(root->val);
        //左边不为空或者左边为空右边不为空，左边需要加括号
        if(root->left||root->right)
        {
            str+='(';
            str+=tree2str(root->left);
            str+=')';
        }
        //右边不为空，右边需要加括号
        if(root->right)
        {
            str+='(';
            str+=tree2str(root->right);
            str+=')';
        }
        return str;
    }
};

2. 二叉树的层序遍历

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*>q;
        size_t levelSize = 0;
        if(root)
        {
            q.push(root);
            levelSize=1;
        }
        vector<vector<int>> vv;
        while(!q.empty())
        {
            //控制一层一层出
            vector<int> v;
            for(size_t i=0;i<levelSize;++i)
            {
                TreeNode* front = q.front();
                q.pop();
                v.push_back(front->val);
                if(front->left)
                    q.push(front->left);
                if(front->right)
                    q.push(front->right);
            }
            vv.push_back(v);
            //当前层出完了，下一层都进队列，队列的size就是下一层的数据个数
            levelSize=q.size();
        }
        return vv;
    }
};

3. 二叉树的层序遍历 II

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        queue<TreeNode*>q;
        size_t levelSize = 0;
        if(root)
        {
            q.push(root);
            levelSize=1;
        }
        vector<vector<int>> vv;
        while(!q.empty())
        {
            //控制一层一层出
            vector<int> v;
            for(size_t i=0;i<levelSize;++i)
            {
                TreeNode* front = q.front();
                q.pop();
                v.push_back(front->val);
                if(front->left)
                    q.push(front->left);
                if(front->right)
                    q.push(front->right);
            }
            vv.push_back(v);
            //当前层出完了，下一层都进队列，队列的size就是下一层的数据个数
            levelSize=q.size();
        }
        reverse(vv.begin(),vv.end());
        return vv;
    }
};

4. 二叉树的最近公共祖先

方法一：O(H*N)

1./**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool Find(TreeNode* sub,TreeNode* x)
    {
        if(sub==nullptr)
            return false;
        return sub == x
            ||Find(sub->left,x)
            ||Find(sub->right,x);
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
    {
        if(root==nullptr)
            return nullptr;
        if(root == p || root == q)
            return root;
        bool pInLeft,pInRight,qInLeft,qInRight;
        pInLeft = Find(root->left,p);
        pInRight = !pInLeft;
        qInLeft = Find(root->left,q);
        qInRight = !qInLeft;
        //1、一个在左一个在右，root就是最近公共祖先
        //2、都在左，递归去左子树找
        //3、都在右，递归去右子树找
        if((pInLeft&&qInRight)||(qInLeft&&pInRight))
        {
            return root;
        }
        else if(pInLeft&&qInLeft)
        {
            return lowestCommonAncestor(root->left,p,q);
        }
        else if(pInRight&&qInRight)
        {
            return lowestCommonAncestor(root->right,p,q);
        }
        else
        {
            //理论上不会走到这里
            return nullptr;
        }
    }
};

方法二：O(N)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool FindPath(TreeNode* root,TreeNode* x,stack<TreeNode*>&path)
    {
        if(root==nullptr)
            return false;
        path.push(root);
        if(root == x)
            return true;
        if(FindPath(root->left,x,path))
            return true;
        if(FindPath(root->right,x,path))
            return true;
        path.pop();
        return false;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        stack<TreeNode*>pPath,qPath;
        FindPath(root,p,pPath);
        FindPath(root,q,qPath);
        //类似链表相交
        while(pPath.size()!=qPath.size())
        {
            if(pPath.size()>qPath.size())
                pPath.pop();
            else
                qPath.pop();
        }
        while(pPath.top()!=qPath.top())
        {
            pPath.pop();
            qPath.pop();
        }
        return pPath.top();
    }
};

5.二叉搜索树与双向链表

1./*
struct TreeNode {
  int val;
  struct TreeNode *left;
  struct TreeNode *right;
  TreeNode(int x) :
      val(x), left(NULL), right(NULL) {
  }
};*/
class Solution {
public:
  void InOrderConvert(TreeNode* cur,TreeNode*& prev)
  {
    if(cur == nullptr)
      return;
    InOrderConvert(cur->left, prev);
    cur->left = prev;
    if(prev)
      prev->right=cur;
    prev = cur;
    InOrderConvert(cur->right, prev);
  }
    TreeNode* Convert(TreeNode* pRootOfTree) {
        TreeNode* prev = nullptr;
    InOrderConvert(pRootOfTree,prev);
    TreeNode* head = pRootOfTree;
    while(head&&head->left)
    {
      head=head->left;
    }
    return head;
    }
};

6.从前序与中序遍历序列构造二叉树

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    TreeNode* _buildTree(vector<int>&preorder,vector<int>&inorder,int& prei,int inbegin, int inend)
    {
        if(inbegin>inend)
            return nullptr;
        TreeNode* root = new TreeNode(preorder[prei++]);
        //分割中序
        int ini=inbegin;
        while(ini <= inend)
        {
            if(inorder[ini] == root->val)
                break;
            else
                ++ini;
        }
        //[inbegin,ini-1] ini [ini+1,inend]
        root->left = _buildTree(preorder,inorder,prei,inbegin,ini-1);
        root->right = _buildTree(preorder,inorder,prei,ini+1,inend);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int i=0;
        return _buildTree(preorder,inorder,i,0,inorder.size()-1);
    }
};

7. 二叉树的前序遍历非递归

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
 //法一
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        if(root==nullptr)return result;
        st.push(root);
        TreeNode* cur=nullptr;
        while(!st.empty())
        {
            cur=st.top();
            st.pop();
            result.push_back(cur->val);
            if(cur->right)st.push(cur->right);
            if(cur->left)st.push(cur->left);
        }
        return result;
    }
};
//法二
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> v;
        TreeNode* cur = root;
        while(cur || !st.empty())
        {
            //开始访问一棵树
            //1、左路节点
            while(cur)
            {
                v.push_back(cur->val);
                st.push(cur);
                cur = cur->left;
            }
            // 2、左路节点的右子树需要访问
            TreeNode*top = st.top();
            st.pop();
            cur = top->right;
        }
        return v;
    }
};

8. 二叉树的中序遍历非递归

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
 //法一
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        TreeNode*cur=root;
        while(cur!=nullptr||!st.empty())
        {
            if(cur!=nullptr)
            {
                st.push(cur);
                cur=cur->left;
            }
            else
            {
                cur=st.top();
                result.push_back(cur->val);
                st.pop();
                cur=cur->right;
            }
        }
        return result;
    }
};
//法二
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> v;
        TreeNode* cur = root;
        while(cur || !st.empty())
        {
            //开始访问一棵树
            //1、左路节点入栈
            while(cur)
            {
                st.push(cur);
                cur = cur->left;
            }
            // 2、当左路节点从栈中出来，表示左子树已经访问过了，应该访问这个节点和它的右节点
            TreeNode*top = st.top();
            st.pop();
            v.push_back(top->val);
            cur = top->right;
        }
        return v;
    }
};

9. 二叉树的后序遍历非递归

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
 //法一
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        if(root==NULL)return result;
        TreeNode*cur=NULL;
        TreeNode*pre=NULL;
        st.push(root);
        while(!st.empty())
        {
            cur=st.top();
            if((cur->left==NULL&&cur->right==NULL)||
            (pre!=NULL&&(pre==cur->left||pre==cur->right)))
            {
                result.push_back(cur->val);
                st.pop();
                pre=cur;
            }
            else
            {
                if(cur->right!=NULL)st.push(cur->right);
                if(cur->left!=NULL)st.push(cur->left);
            }
        }
        return result;
    }
};
//法二
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> v;
        TreeNode* cur = root;
        TreeNode* prev = nullptr;
        while(cur || !st.empty())
        {
            //开始访问一棵树
            //1、左路节点入栈
            while(cur)
            {
                st.push(cur);
                cur = cur->left;
            }
            // 2、当左路节点从栈中出来，表示左子树已经访问过了
            TreeNode*top = st.top();
            //栈顶节点右子树为空或者上一个访问节点是右子树的根，说明右子树已经访问过了，可以访问上一个节点的右数
            //否则 子问题访问top的右子树
            if(top->right == nullptr||top->right == prev)
            {
                v.push_back(top->val);
                prev = top;
                cur = nullptr;
                st.pop();
            }
            else{
                cur = top->right;//子问题访问右子树
            }
        }
        return v;
    }
};
文章标签：
算法
幼稚十一
目录
相关文章
Boale_H
|
移动开发 前端开发 iOS开发
记录一下前端H5的复制功能在ios端的兼容性问题
记录一下前端H5的复制功能在ios端的兼容性问题
Boale_H
1356 0
小王老师呀
|
存储 SQL 关系型数据库
MySQL 大表拆分
【9月更文挑战第13天】在 MySQL 中，为解决大数据量导致的性能问题，常采用表拆分策略，主要包括水平拆分和垂直拆分。水平拆分按规则将大表拆成多个小表，如范围划分（按时间或 ID）和哈希划分（按字段哈希值）。垂直拆分则按字段相关性拆分，减少表宽度。拆分需注意数据迁移、应用改造、索引优化及分布式事务处理等问题。实施前应充分评估和测试。
小王老师呀
1133 8
john散漫
|
UED
页面导入样式时，使用 link 和 @import 有什么区别？
【10月更文挑战第5天】
john散漫
482 58
阿里云云原生
|
人工智能 搜索推荐 测试技术
AI 辅助编程的效果衡量
本文主要介绍了如何度量研发效能，以及 AI 辅助编程是如何影响效能的，进而阐述如何衡量 AI 辅助编程带来的收益。
阿里云云原生
1771 6
阿里云安全_
|
4天前
|
云安全 人工智能 算法
以“AI对抗AI”，阿里云验证码进入2.0时代
三层立体防护，用大模型打赢人机攻防战
阿里云安全_
1313 3
阿里云安全_
|
2天前
|
安全
体检通知：阿里云2026年度云上安全健康体检即将开启！
1月初正式上线！
阿里云安全_
1257 6
bailiantest1
|
4天前
|
机器学习/深度学习 安全 API
MAI-UI 开源：通用 GUI 智能体基座登顶 SOTA！
MAI-UI是通义实验室推出的全尺寸GUI智能体基座模型，原生集成用户交互、MCP工具调用与端云协同能力。支持跨App操作、模糊语义理解与主动提问澄清，通过大规模在线强化学习实现复杂任务自动化，在出行、办公等高频场景中表现卓越，已登顶ScreenSpot-Pro、MobileWorld等多项SOTA评测。
bailiantest1
653 3
游客p3shvhj26rigq
|
5天前
|
人工智能 Rust 运维
这个神器让你白嫖ClaudeOpus 4.5，Gemini 3！还能接Claude Code等任意平台
加我进AI讨论学习群，公众号右下角“联系方式”文末有老金的 开源知识库地址·全免费
游客p3shvhj26rigq
663 11
bailiantest1
|
11天前
|
编解码 人工智能 自然语言处理
⚽阿里云百炼通义万相 2.6 视频生成玩法手册
通义万相Wan 2.6是全球首个支持角色扮演的AI视频生成模型，可基于参考视频形象与音色生成多角色合拍、多镜头叙事的15秒长视频，实现声画同步、智能分镜，适用于影视创作、营销展示等场景。
bailiantest1
759 5

热门文章

最新文章

  • 1
    RPA学习第一课 --初识RPA
  • 2
    Kubernetes中的Pod无法访问外网-Ubuntu16.04 LTS
  • 3
    docker启动容器时报错：iptables: No chain/target/match by that name
  • 4
    C++ ＜windows.h＞库函数探究初步：句柄操作
  • 5
    Eclipse Oxygen 如何正确配置Java 9 SDK
  • 6
    阿里云Intel Xeon Platinum 8269CY（Cascade Lake）处理器CPU性能评测
  • 7
    python获取pdf和word文档页数
  • 8
    redolog文件头简单探究
  • 9
    IbatisNet支持2.0的版本Release 发布了
  • 10
    【Oracle】在线重定义表
  • 1
    2026年阿里云服务器租用价格表（一年/按月/按小时报价明细）
    60
  • 2
    2026年阿里云服务器租用收费标准与最新活动价格表，手动整理
    64
  • 3
    Lux 上手指南：让 AI 直接操作你的电脑
    42
  • 4
    技术人视角：传统产品经理如何系统性转型AI产品经理
    53
  • 5
    Web3 的真相：天天喊去中心化，可中心到底“藏”在哪？
    40
  • 6
    容器跑起来才是危险的开始：聊聊 Falco + eBPF + 行为检测这套“运行时安全真功夫”
    35
  • 7
    Flink 最近又“进化”了：状态后端与 Savepoint，真不是背概念那么简单
    28
  • 8
    libicu-62.1-6.ky10.x86_64.rpm 安装步骤详解（麒麟V10系统）
    31
  • 9
    什么是 Code 39?
    83
  • 10
    基于深度学习的水稻病虫害检测系统
    30

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    基于Python+Vue开发的口腔牙科预约管理系统