二叉樹題目匯總

二叉樹題目匯總

我個(gè)人把涉及到二叉樹的這15到題分為4種大類，以供參考

• 打印類

  • 從上到下打印
    - 不分行
    - 分行
  • 之字型

• 性質(zhì)類

  • 對(duì)稱類
    • 求樹的鏡像
    • 判斷是否為對(duì)稱二叉樹
  • 平衡類
    • 判斷是否為平衡二叉樹
  • 存在類/判斷類
    • 是否包含（存在）某一子結(jié)構(gòu)
    • 是否存在和為某一值的路徑
    • 某一序列是否為二叉樹的后序遍歷

• 參數(shù)類

  • 二叉樹的深度
  • 二叉樹的下一個(gè)結(jié)點(diǎn)
  • 搜索二叉樹的第K個(gè)節(jié)點(diǎn)

• 重建（轉(zhuǎn)換）類

  • 根據(jù)中序和先序重建二叉樹 【字符串】
  • 轉(zhuǎn)化為雙向鏈表 【鏈表】
  • 序列化和反序列化 【字符串】

具備的基本能力

• 二叉樹的前/中/后/層次遍歷
  • 遞歸
  • 非遞歸
• 樹的相關(guān)概念的區(qū)別
  • 二叉樹 平衡二叉樹 二叉搜索樹 滿二叉樹 完整二叉樹
  • 高度 深度

1.打印類

22.從上往下打印二叉樹

從上往下打印出二叉樹的每個(gè)節(jié)點(diǎn)，同層節(jié)點(diǎn)從左至右打印。

/*
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.把二叉樹打印成多行

從上到下按層打印二叉樹，同一層結(jié)點(diǎn)從左至右輸出。每一層輸出一行。

    /*
    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.按照之字形順序打印二叉樹

請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)按照之字形打印二叉樹，即第一行按照從左到右的順序打印，第二層按照從右至左的順序打印，第三行按照從左到右的順序打印，其他行以此類推

/*
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;
        // 加標(biāo)志位，奇數(shù)行 左->右  偶數(shù)行  右-> 左
       
        while(q.size()){
            
            //vector<int> path;
            int size= q.size();
            for(int i=0;i<size;i++){  
                //注意 這里  i<q.size()  不能這么寫 因?yàn)殛?duì)列是動(dòng)態(tà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);     
               }
            if(!flag) reverse(path.begin(),path.end());
            flag=!flag;
            res.push_back(path);
            path.clear();
        
        }
        return res;

    }
    
};

2.性質(zhì)類

• 對(duì)稱類

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.對(duì)稱的二叉樹

請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，用來判斷一顆二叉樹是不是對(duì)稱的。注意，如果一個(gè)二叉樹同此二叉樹的鏡像是同樣的，定義其為對(duì)稱的

/*
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 ;  
        // 有一個(gè)為空，返回false,兩個(gè)都空的話返回 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.樹的子結(jié)構(gòu)

輸入兩棵二叉樹A，B，判斷B是不是A的子結(jié)構(gòu)。（ps：我們約定空樹不是任意一個(gè)樹的子結(jié)構(gòu)）

/*
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);
        //遞歸枚舉  先枚舉左邊 若沒有，再枚舉右邊
    }
    //判斷 第二棵數(shù)的點(diǎn)是不是在第一課樹上都有對(duì)應(yīng)的點(diǎn)
     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.二叉搜索樹的后續(xù)遍歷序列

輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹的后序遍歷的結(jié)果。如果是則輸出Yes,否則輸出No。假設(shè)輸入的數(shù)組的任意兩個(gè)數(shù)字都互不相同。

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.二叉樹中和為某一值的路徑

輸入一顆二叉樹的根節(jié)點(diǎn)和一個(gè)整數(shù)，打印出二叉樹中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑。路徑定義為從樹的根結(jié)點(diǎn)開始往下一直到葉結(jié)點(diǎn)所經(jīng)過的結(jié)點(diǎn)形成一條路徑。(注意: 在返回值的list中，數(shù)組長度大的數(shù)組靠前)

/*
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.參數(shù)類

38.二叉樹的深度

輸入一棵二叉樹，求該樹的深度。從根結(jié)點(diǎn)到葉結(jié)點(diǎn)依次經(jīng)過的結(jié)點(diǎn)（含根、葉結(jié)點(diǎn)）形成樹的一條路徑，最長路徑的長度為樹的深度。

/*
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() 不能這樣寫 因?yàn)槭莿?dòng)態(tài)變化的
                TreeNode* node=q.front();
                q.pop();
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);   
            }
        }
            
        return res;  
    }
};

57.二叉樹的下一個(gè)結(jié)點(diǎn)

給定一個(gè)二叉樹和其中的一個(gè)結(jié)點(diǎn)，請(qǐng)找出中序遍歷順序的下一個(gè)結(jié)點(diǎn)并且返回。注意，樹中的結(jié)點(diǎn)不僅包含左右子結(jié)點(diǎn)，同時(shí)包含指向父結(jié)點(diǎn)的指針。

/*
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){ // 找右子樹左邊的那個(gè)
            p=p->right; 
            while(p->left){
                p=p->left;
            }
            return p;
        }
        while(p->next && p == p->next->right) p=p->next; 
        //進(jìn)不去的條件是找到了上面的第一個(gè)做左孩子的子節(jié)點(diǎn) 
        return p->next;
    }
};

62.二叉搜索樹的第K個(gè)結(jié)點(diǎn)

給定一棵二叉搜索樹，請(qǐng)找出其中的第k小的結(jié)點(diǎn)。例如， （5，3，7，2，4，6，8） 中，按結(jié)點(diǎn)數(shù)值大小順序第三小結(jié)點(diǎn)的值為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.重建（轉(zhuǎn)換）類

4.重建二叉樹

輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請(qǐng)重建出該二叉樹。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。例如輸入前序遍歷序列{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.二叉搜索樹與雙向鏈表

輸入一棵二叉搜索樹，將該二叉搜索樹轉(zhuǎn)換成一個(gè)排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只能調(diào)整樹中結(jié)點(diǎn)指針的指向

/*
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.序列化二叉樹

請(qǐng)實(shí)現(xiàn)兩個(gè)函數(shù)，分別用來序列化和反序列化二叉樹

二叉樹的序列化是指：把一棵二叉樹按照某種遍歷方式的結(jié)果以某種格式保存為字符串，從而使得內(nèi)存中建立起來的二叉樹可以持久保存。序列化可以基于先序、中序、后序、層序的二叉樹遍歷方式來進(jìn)行修改，序列化的結(jié)果是一個(gè)字符串，序列化時(shí)通過 某種符號(hào)表示空節(jié)點(diǎn)（#），以 ！ 表示一個(gè)結(jié)點(diǎn)值的結(jié)束（value!）。

二叉樹的反序列化是指：根據(jù)某種遍歷順序得到的序列化字符串結(jié)果str，重構(gòu)二叉樹。

/*
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); //注意函數(shù)的返回值
        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;
        }
        //把字符轉(zhuǎn)換成節(jié)點(diǎn)
        int num=0;
        while(**str!='\0' && **str != '!'){
            num=num*10+((**str)-'0');
            ++(*str);
        }
        TreeNode *root=new TreeNode(num);
        // 轉(zhuǎn)化完畢，查看是否還有未轉(zhuǎn)換的節(jié)點(diǎn)。
        // 到達(dá)字符串末尾即轉(zhuǎn)換完畢
        if(**str=='\0') return root;
        else (*str)++;
        root->left=dfs_d(str);
        root->right=dfs_d(str);
        return root;
    }
};