【刷题】剑指OFFER 二叉树专题整理

二叉树题目汇总

我个人把涉及到二叉树的这15到题分为4种大类，以供参考

打印类
- 从上到下打印
  - 不分行
  - 分行
- 之字型
性质类
- 对称类
  - 求树的镜像
  - 判断是否为对称二叉树
- 平衡类
  - 判断是否为平衡二叉树
- 存在类/判断类
  - 是否包含（存在）某一子结构
  - 是否存在和为某一值的路径
  - 某一序列是否为二叉树的后序遍历

参数类
- 二叉树的深度
- 二叉树的下一个结点
- 搜索二叉树的第K个节点
重建（转换）类
- 根据中序和先序重建二叉树【字符串】
- 转化为双向链表【链表】
- 序列化和反序列化【字符串】

具备的基本能力

二叉树的前/中/后/层次遍历
- 递归
- 非递归
树的相关概念的区别
- 二叉树平衡二叉树二叉搜索树满二叉树完整二叉树
- 高度深度

1.打印类

22.从上往下打印二叉树

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    vector<int> PrintFromTopToBottom(TreeNode* root) {
        
        vector<int> res; 
        if(!root) return res;
        
        queue<TreeNode*> queueNode;
        queueNode.push(root);
        
        while(queueNode.size()){
             TreeNode* pNode=queueNode.front();
             queueNode.pop();
             res.push_back(pNode->val);
            if(pNode->left) queueNode.push(pNode->left);
            if(pNode->right) queueNode.push(pNode->right);
                  
        }
        return res;
    }
};

60.把二叉树打印成多行

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

    /*
    struct TreeNode {
        int val;
        struct TreeNode *left;
        struct TreeNode *right;
        TreeNode(int x) :
                val(x), left(NULL), right(NULL) {
        }
    };
    */
    class Solution {
    public:
            vector<vector<int> > Print(TreeNode* root) {
                vector<vector<int>> res;
                if(!root) return res;
                
                queue<TreeNode*> q;
                q.push(root);
                
                while(q.size()){
                    int size=q.size();
                    vector<int> path;
                    for(int i=0;i<size;i++){
                        auto front=q.front();
                        path.push_back(front->val);
                        q.pop();
                        if(front->left) q.push(front->left);
                        if(front->right) q.push(front->right);
                     }
                     res.push_back(path);
                    
                }
                return res;
            
            }
        
    };

59.按照之字形顺序打印二叉树

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    vector<vector<int> > Print(TreeNode* p) {
        vector<vector<int>> res;
        vector<int> path;
        if(!p) return res;
        
        queue<TreeNode*> q;
        q.push(p);
        bool flag=true;
        // 加标志位，奇数行 左->右  偶数行  右-> 左
       
        while(q.size()){
            
            //vector<int> path;
            int size= q.size();
            for(int i=0;i<size;i++){  
                //注意 这里  i<q.size()  不能这么写 因为队列是动态变化的
                auto front=q.front();
                path.push_back(front->val);
                q.pop();
                if(front->left) q.push(front->left);
                if(front->right) q.push(front->right);     
               }
            if(!flag) reverse(path.begin(),path.end());
            flag=!flag;
            res.push_back(path);
            path.clear();
        
        }
        return res;

    }
    
};

2.性质类

对称类

18.二叉树的镜像

操作给定的二叉树，将其变换为源二叉树的镜像

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    void Mirror(TreeNode *pRoot) {
        if (pRoot==NULL || (pRoot->left== NULL && pRoot->right==NULL)){
            return;
        }
        TreeNode *temp=pRoot->left;
        pRoot->left=pRoot->right;
        pRoot->right=temp;
        if(pRoot->left){
            Mirror(pRoot->left);
        }
        if(pRoot->right){
            Mirror(pRoot->right);
        }
        return;
    }
};

58.对称的二叉树

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    
    bool isSymmetrical(TreeNode* p)
    {
         if(!p) return true;
         return dfs(p->left,p->right);
    }
    bool dfs(TreeNode * p,TreeNode * q ){
        if(!p || !q)  return  !p && !q ;  
        // 有一个为空，返回false,两个都空的话返回 true
        if( p->val != q->val) return false;
        return dfs(p->left,q->right) && dfs(p->right,q->left);
    }

};

平衡类

39.平衡二叉树

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

class Solution {
public:
    bool ans = true;
    bool IsBalanced_Solution(TreeNode* p) {
        dfs(p);
        return ans;
    }
    int dfs (TreeNode* p){
        if (!p) return 0;
        int left = dfs(p->left),right=dfs(p->right);
        if (abs(left-right)>1) ans=false;
        return max(left,right)+1;
    };
};

存在类

17.树的子结构

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
    {
        if(!pRoot1||!pRoot2)  return false;
        if(isPart(pRoot1,pRoot2)) return true;
        return HasSubtree(pRoot1->left,pRoot2)|| HasSubtree(pRoot1->right,pRoot2);
        //递归枚举  先枚举左边 若没有，再枚举右边
    }
    //判断 第二棵数的点是不是在第一课树上都有对应的点
     bool isPart(TreeNode *p1,TreeNode *p2) {
         if(!p2) return true; // 第二课树空了，说明之前的都匹配上了
         if(!p1||p1->val != p2->val) return false;
         return isPart(p1->left,p2->left) && isPart(p1->right,p2->right);
           }

};

23.二叉搜索树的后续遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

class Solution {
public:
    vector<int> seq;
    
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.empty()) return false;
        seq=sequence;
        return dfs(0,seq.size()-1);

    }
    bool dfs(int l, int r){
        if(l>=r) return true;
        int root = seq[r];
        int k=l;
        while(k<r && seq[k]< root) k++;
        for (int i= k;i<r;i++){
            if (seq[i]<root) return false;
        }
        return dfs(l,k-1)&& dfs(k,r-1);
    }
};

24.二叉树中和为某一值的路径

输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        
        if(!root || expectNumber <= 0) return res;
        dfs(root,expectNumber);
        return res;
    }
    void  dfs(TreeNode* p ,int sum)
    { 
        if(!p) return ;
        path.push_back(p->val);
        sum=sum-p->val;
        if(!p->left&&!p->right&&!sum) res.push_back(path);
        dfs(p->left,sum);
        dfs(p->right,sum);
        path.pop_back();
    }
};

3.参数类

38.二叉树的深度

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

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


class Solution {
public:
    int TreeDepth(TreeNode* p)
    {
        int res=0;
        if(!p) return res;
        
        queue<TreeNode*> q;
        q.push(p);
        
        while(q.size()){
            res++;
            int num = q.size();
            for(int i =0; i < num; i++){  // i<q.size() 不能这样写 因为是动态变化的
                TreeNode* node=q.front();
                q.pop();
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);   
            }
        }
            
        return res;  
    }
};

57.二叉树的下一个结点

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

/*
struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next;
    TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
        
    }
};
*/
class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* p)
    {
        if (p->right){ // 找右子树左边的那个
            p=p->right; 
            while(p->left){
                p=p->left;
            }
            return p;
        }
        while(p->next && p == p->next->right) p=p->next; 
        //进不去的条件是找到了上面的第一个做左孩子的子节点 
        return p->next;
    }
};

62.二叉搜索树的第K个结点

给定一棵二叉搜索树，请找出其中的第k小的结点。例如，（5，3，7，2，4，6，8）中，按结点数值大小顺序第三小结点的值为4

class Solution {
public:
    TreeNode* KthNode(TreeNode* pRoot, int k)
    {   
        if(pRoot == NULL) return NULL;
        return dfs(pRoot,k) ;
    }
    
    TreeNode* dfs(TreeNode* pRoot, int& k)
    {
        TreeNode* target = NULL;
        if(pRoot->left !=NULL) 
            target = dfs(pRoot->left,k);
         k--;
         if(k==0){
            target = pRoot;
            return target;
         }
        if(target == NULL && pRoot->right !=NULL && k>0) 
            target = dfs(pRoot->right,k);
        return target;
    }
};

4.重建（转换）类

4.重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if ( pre.empty()|| vin.empty()) return NULL;
        int root_val=pre[0];
        TreeNode *root=new TreeNode(root_val);
        int leftLength=0;
        int rightLength=0;
        for (int i=0;i<vin.size();i++)
        {
            if (vin[i]==root_val)
            {
                leftLength=i;
                rightLength=vin.size()-i-1;
                break;
            }
        }
        vector<int> in_left,in_right,pre_left,pre_right;
        for(int j=0;j<leftLength;j++)
        {
            in_left.push_back(vin[j]);
            pre_left.push_back(pre[j+1]);
        }
        for(int j=0;j<rightLength;j++)
        {
            in_right.push_back(vin[leftLength+1+j]);
            pre_right.push_back(pre[1+leftLength+j]);
        }
        root->left=reConstructBinaryTree(pre_left,in_left);
        root->right=reConstructBinaryTree(pre_right,in_right);
        return root;
    }
};

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

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    TreeNode* Convert(TreeNode* root)
    {
        if(!root) return NULL;
        auto sides=dfs(root);
        return sides.first;
    }
    
    pair<TreeNode*,TreeNode*> dfs(TreeNode* root){
        
        if(!root->left&& !root->right) return {root,root};
        if(root->left&&root->right){
            auto lsides=dfs(root->left),rsides=dfs(root->right);
            lsides.second->right=root;root->left=lsides.second;
            rsides.first->left=root;root->right=rsides.first;
            return{lsides.first,rsides.second};
        }
        if(root->left){
            auto lsides=dfs(root->left);
            lsides.second->right=root,root->left=lsides.second;
            return{lsides.first,root};
        }
        if(root->right){
            auto rsides=dfs(root->right);
            root->right=rsides.first,rsides.first->left=root;
            return{root,rsides.second};
        }
    }
    
};

61.序列化二叉树

请实现两个函数，分别用来序列化和反序列化二叉树

二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过某种符号表示空节点（#），以！表示一个结点值的结束（value!）。

二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    char* Serialize(TreeNode *root) {    
        if(! root) return NULL;
        string str;
        dfs_s(root ,str); //注意函数的返回值
        char *res =new char[str.size()+1];
        int i;
        for(i=0;i<str.size();i++){
            res[i]=str[i];
        }
        res[i]='\0';
        return res;
    }
    
    void dfs_s(TreeNode *root,string &str){
        if(root==NULL){
            str+='#';
            return ;
        }
        str+=to_string(root->val);
        str+='!';
        dfs_s(root->left,str);
        dfs_s(root->right,str);
    }
    
    TreeNode* Deserialize(char *str) {
        if(str == NULL) return NULL;
        TreeNode* res=dfs_d(&str);
        return res;
    }
    
    TreeNode* dfs_d(char **str){
        if(**str == '#'){
            ++(*str);
            return NULL;
        }
        //把字符转换成节点
        int num=0;
        while(**str!='\0' && **str != '!'){
            num=num*10+((**str)-'0');
            ++(*str);
        }
        TreeNode *root=new TreeNode(num);
        // 转化完毕，查看是否还有未转换的节点。
        // 到达字符串末尾即转换完毕
        if(**str=='\0') return root;
        else (*str)++;
        root->left=dfs_d(str);
        root->right=dfs_d(str);
        return root;
    }
};

最后编辑于：2019.10.08 17:52:01

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 203,456评论 5赞 477
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,370评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 150,337评论 0赞 337
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,583评论 1赞 273
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,596评论 5赞 365
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,572评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,936评论 3赞 395
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,595评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,850评论 1赞 297
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,601评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,685评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,371评论 4赞 318
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,951评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,934评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,167评论 1赞 259
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 43,636评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,411评论 2赞 342