劍指offer 刷題3

二十四二叉樹中和為某一值的路徑3/2

二十六二叉搜尋樹與雙向連結清單

三十八二叉樹的深度

三十九平衡二叉樹

五十八二叉樹的下一個節點

對稱的二叉樹

二叉搜尋樹的第k個節點

按之字順序列印二叉樹3/3

二叉樹列印成多行

序列化二叉樹

二十四二叉樹中和為某一值的路徑3/2

參考：https://www.cnblogs.com/silentteller/p/10829084.html

參考：https://www.cnblogs.com/silentteller/p/11925160.html

參考：https://www.cnblogs.com/wanglei5205/p/8686863.html

【前序周遊】【全局變量】

三個連結裡分别增加了全局變量，使得函數參數減少，一定程度上減少了麻煩。

思路：

1 使用二維向量res存儲全部路徑，使用一維向量s存儲目前路徑。

2 周遊二叉樹的過程：按前序周遊順序通路每一個節點。通路每個結點時，将結點添加到路徑向量tmp中。如果目前結點是葉子結點，則判斷目前路徑是否是符合條件的路徑，符合條件的路徑存入到二維向量res；如果目前結點不是葉子結點，則遞歸目前節點的左右子節點。

/*
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> > FindPath(TreeNode* root,int expectNumber) {
        if(root) dfs(root, expectNumber);
        else return res;

    }
    void  dfs(TrrNode * root, int sum){
        s.push_back(root);//先序周遊，通路每個結點時，将結點添加到路徑向量s。
        if（！（root -> left） && !(root -> right)){//是葉節點
            if(sum - root -> val == 0)//則判斷目前路徑是否是符合條件的路徑，
                res.push_back(s);//符合條件的路徑存入到二維向量res
        }else{//不是葉節點，分别遞歸左右子樹
            if(root -> left) dfs(root -> left, sum - root -> val);
            if(root -> right) dfs(root -> right, sum - root -> val);
        }
        
        if(!s.empty())//s非空
            s.pop_back();傳回父節點之前需要删除目前節點
    }
 private:
    vector<vector<int>> res;//二維向量res存儲全部路徑
    vector<int> s;//一維向量s存儲目前路徑
};

二十六二叉搜尋樹與雙向連結清單

參考：https://www.cnblogs.com/silentteller/p/11942608.html

【中序周遊】【雙向連結清單】

class Solution {
public:
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        if(pRootOfTree == nullptr)
            return nullptr;//空樹
        if(pRootOfTree -> left == nullptr && pRootOfTree -> right == nullptr)
            return pRootOfTree;//隻有一個元素
        helper(pRootOfTree);//完成中序周遊
        for(int i = 0; i < node.size() - 1; i++){//按順序連接配接所有節點，循環到size-1節點停下
            node[i] -> right = node[i + 1];//前後互連 node0為頭結點
            node[i + 1] -> left = node[i];//【易錯】【雙向連結清單的連接配接】
        }
        return node[0];//傳回連結清單頭結點
    }
    
    void helper(TreeNode* root){
        if(root == nullptr)
            return;
        helper(root -> left);//中序周遊
        node.push_back(root);//node作為私有變量，存儲中序周遊結果
        helper(root -> right);
    }
private:
    vector<TreeNode*> ndoe;//一維向量存儲節點
};

三十八二叉樹的深度

參考：https://www.cnblogs.com/silentteller/p/12046692.html

【深度】

深度 = max（左子樹高度，右子樹高度）+1；

遞歸直到葉節點，停止條件：葉節點->left == nullptr, return 0;

class Solution {
public:
    int TreeDepth(TreeNode* pRoot)
    {
    
        if(pRoot == nullptr) return 0;
        else return THeight(pRoot);
    }
    int THeight(TreeNode* root){
        if(root == nullptr)
            return 0;
        else
            return max(THeight(root -> left) + 1,THeight(root -> right) + 1);//+1放在max（）的裡面
    }
};

三十九平衡二叉樹

參考：https://www.cnblogs.com/wanglei5205/p/8918624.html

參考：https://blog.csdn.net/dawn_after_dark/article/details/81702988

參考：https://www.cnblogs.com/silentteller/p/12051453.html

【二叉樹高度】

class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
//平衡二叉樹：abs(左子樹高度 - 右子樹高度)<=1
//計算二叉樹高度：遞歸找到葉節點
//-1表示false
        if(getHeight(pRoot) == -1)
            return false;
        else
            return true;
    }
    
    int getHeight(TreeNode* root){
        if(root == nullptr)
            return 0;
        int LeftHeight = getHeight(root -> left);
        if(LeftHeight == -1) return -1;
        int RightHeight = getHeight(root -> right);
        if(RightHeight == -1) return -1;
        return abs(LeftHeight - RightHeight) <= 1? max(LeftHeight + 1, RightHeight + 1): -1;
    }
};

五十八二叉樹的下一個節點

參考：https://www.cnblogs.com/silentteller/p/12114894.html

二叉樹的中序周遊是左根右，是以如果一個結點的右子樹不為空，那麼這個節點的下一個節點一定是右子樹的最左結點，如果右子樹不存在左子樹的話，就傳回右子樹的根結點。

如果一個結點的右子樹為空，且目前結點是其父結點的左子樹的根結點，那麼直接傳回其父節點，否則就一直通路其父結點，直到找到一個結點是其父結點的左子結點，同樣傳回其父結點。

【中序周遊】【父指針】【邏輯】

這題一定要畫樹

class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode)
    {//中序周遊下一個節點是右兒子
        if(pNode == nullptr) return pNode;
        if(pNode->right != nullptr){//節點右兒子存在
            pNode = pNode -> right;//指針移到右兒子上
            while(pNode -> left != nullptr)//找到右子樹中最左邊（最小）節點
                pNode = pNode -> left;
            return pNode;
        }
        while(pNode -> next != nullptr && pNode -> next->left != pNode){
            pNode = pNode -> next;//右子樹不存在，一直向上找爸爸，直到找到一個爸爸是爺爺的左兒子。當找到根節點時候，他沒有父指針，是以傳回NULL
        }
        return pNode->next;//傳回父節點

    }
};

對稱的二叉樹

參考：https://www.cnblogs.com/silentteller/p/12114934.html

與鏡像的差別，鏡像是将樹左右子樹一直交換，交換的元素值可以不同

對稱是左右兩邊必須是相同的數字

class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot)
    {
    
        if(pRoot == nullptr)
            return true;//空樹對稱
        return isDuichen(pRoot->left, pRoot -> right);
    }
    bool isDuichen(TreeNode* p1, TreeNode* p2){
        if(p1 == nullptr && p2 == nullptr)
            return true;//出口A 比較到左右樹都空了
        if(p1 == nullptr && p2 != nullptr)
            return false;//出口B
        if(p2 == nullptr && p1 != nullptr)
            return false;//出口C 一個空一個不空
        if(p1->val != p2->val)
            return false;//兩者非空，但值不相同
        return isDuichen(p1->left,p2->right)&&isDuichen(p1->right,p2->left);
        //【注意】比較的是最左和最右，中間兩個互相比較；ABCD比較AD和BC
    }

};

二叉搜尋樹的第k個節點

參考：https://www.cnblogs.com/silentteller/p/12118658.html

二叉搜尋樹的中序周遊結果正好是按數值升序排列的結果，我們可以利用中序周遊将結點按val值的順序存儲到數組中，然後直接按索引傳回即可。

【中序周遊】

class Solution {
public:
    TreeNode* KthNode(TreeNode* pRoot, int k)
    {
        if(pRoot == nullptr) return nullptr;
        LDR(pRoot);
        if(k>res.size() || k<1)
            return nullptr;
        return res[k - 1];
          
    }
    void LDR(TreeNode* root){
        if(root == nullptr)
            return;
        LDR(root->left);
        res.push_back(root);
        LDR(root->right);
    }

private:
    vector<TreeNode*> res;
};

按之字順序列印二叉樹3/3

參考：https://www.cnblogs.com/silentteller/p/12115122.html

“實際上是二叉樹的層次周遊，隻不過每一行輸出的方向都是相反的，每周遊二叉樹的結點時，都将其内的每一個結點的左右孩子都儲存好，設定一個标志，ture時就正序輸出，false就逆序輸出val，直到所有的結點都列印完即可。”

參考：https://yq.aliyun.com/articles/368042

劍指offer 刷題3

思路：【層序周遊】+搞一個flag來标志是正向還是負向列印，列印完一行取反

層序周遊一般方法：隊列，node出隊，node左右兒子入隊

本題思路：

A是列印行，B是列印行的兒子，考慮輸出方向，C作為輸出行；res(全局變量)儲存所有結果，儲存C

1 根節點壓入A，

開始while循環，循環條件 A非空

2 A非空，将A中元素a的左右兒子bc壓入B

3判斷flag，真：A從左往右掃描輸出（for循環 O（n））

假：A從右往左掃描輸出

掃描輸出結果存入C

4 flag取反

5 将C壓入res

6 交換AB，清空B

最終調出循環條件是：A中節點 == NULL

即通路到葉節點的兒子那一層，則跳出while循環

class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        if(pRoot == nullptr) return res;
        vector<TreeNode*> A;
        vector<TreeNode*> B;
        bool flag = true;
        
        A.push_back(pRoot);
        while(!A.empty()){
            for(auto i:A){//【錯了一次】【掃描A中元素的左右兒子】
                if(i->left != nullptr) B.push_back(i->left);
                if(i->right != nullptr) B.push_back(i->right);
            }
            
            
            vector<int> C;
            if(flag){
                //從左往右輸出
                for(int i = 0; i < A.size(); i++){
                    C.push_back(A[i]->val);//C是int類型，要壓入數字，不要忘記->val
                }
            }else{
                //從右往左輸出
                for(int i = A.size() - 1; i >= 0; i--)
                    C.push_back(A[i]->val);
            }
            flag = !flag;
            res.push_back(C);
            
            A.swap(B);
            B.clear();
        }
        return res;
    }
private:
    vector<vector<int>> res;
};

二叉樹列印成多行

【層次周遊】

和上一題差不多，不需要flag和C

A是列印行，B是列印行的兒子；res儲存所有結果，儲存A

1 根節點壓入A，

開始while循環，循環條件 A非空

2 A非空，将A中元素a的左右兒子bc壓入B

3 A從左往右掃描輸出（for循環 O（n））

輸出結果存入C

4 将C壓入res

5 交換AB，清空B

最終調出循環條件是：A中節點 == NULL

即通路到葉節點的兒子那一層，則跳出while循環

/*
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* pRoot) {
        
            if(pRoot == nullptr)
                return res;
            vector<TreeNode*> A,B;
            
            
            A.push_back(pRoot);
            while(!A.empty()){
                for(auto i:A){
                    if(i->left) B.push_back(i->left);
                    if(i->right) B.push_back(i->right);
                }
                vector<int> C;
                for(int i = 0; i < A.size(); i++){
                    C.push_back(A[i]->val);
                }
                res.push_back(C);
                A.swap(B);
                B.clear();
            }
            return res;
        }
private:
    vector<vector<int>> res;
};

序列化二叉樹

參考：https://blog.csdn.net/mbskypan/article/details/89676923?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task

劍指offer 刷題3

參考：https://www.cnblogs.com/silentteller/p/12115563.html

思路：

序列化：把樹列印成一串字元

反序列化：把一串字元，重建成二叉樹

簡單地來看就是列印樹和重建樹

對于序列化：

a：全局變量，int型一維向量

res：儲存結果，int型數組

1 根節點是否為空，是->a中壓入‘#’字元

2根節點非空，對二叉樹進行前序周遊，将a中元素複制到res；

res為動态數組，根據a的大小建立

3 res強制轉換為字元型，傳回res

對于反序列化：

1，将輸入字元串數組 str 強制轉換成int類型數組 p

2，處理p

怎麼處理呢？

1 檢查p第一個元素是否為#，是->指針後移，傳回null，退出遞歸；【這裡的指針後移，是指到了左/右子樹的葉節點，要繼續移動指針，通路另一個子樹】

2 否-> 建立一個樹節點res，後移指針，樹的左兒子 = 遞歸處理；樹的右兒子 = 遞歸處理；

3傳回

/*
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) {//傳回字元型數組類型   
        Dlr(root);對二叉樹進行前序周遊将節點加入數組
        //将vector數組a中的元素一一複制到動态整型數組res中
        int *res = new int[a.size()];
        for(int i = 0;i < a.size(); i++) 
            res[i] = a[i];//複制【易錯：忘記複制了】
        return (char*)res;//傳回字元型數組類型
    }
    
    TreeNode* Deserialize(char *str) {
        int *p = (int*) str;//強制轉換，先将字元數組類型轉為整型數組
        return helper(p);//二叉樹的節點的值就可以直接從整型數組中得到
    }
    TreeNode* helper(int *&str) {//【易錯：&對p的引用改變p的值】
        if(*str == 0xFFFFFFFF){//處理遞歸出口，如果遇到0xFFFFFFF，
            str++;//則指針向後移動一個機關
            return nullptr;//并退出遞歸【易錯：傳回類型寫錯了】
        }
        //否則
        TreeNode* res = new TreeNode(*str);//構造二叉樹根節點【易錯：竟然寫成了str，str是下标啊】
        str++;//繼續移動指針
        res->left = helper(str);
        res->right = helper(str);//連接配接遞歸得到的左子樹以及右子樹
        return res;//傳回二叉樹根節點【忘記傳回了】
    }
    //前序周遊
    void Dlr(TreeNode *root){
        if(root == nullptr){//當節點為空的時候，
            a.push_back(0xFFFFFFFF);//加入特殊數值0xFFFFFFF，
            return;//并退出遞歸【結束循環，傳回空】
        }
        a.push_back(root->val);//【壓入的是節點的值，要厘清楚壓入的是啥】
        Dlr(root->left);
        Dlr(root->right);
    }
private:
    vector<int> a;
};

劍指offer 刷題3

二十四二叉樹中和為某一值的路徑3/2

二十六二叉搜尋樹與雙向連結清單

三十八二叉樹的深度

三十九平衡二叉樹

五十八二叉樹的下一個節點

對稱的二叉樹

二叉搜尋樹的第k個節點

按之字順序列印二叉樹3/3

二叉樹列印成多行

序列化二叉樹

繼續閱讀

C語言第四章自述2第四章選擇結構程式設計

面試題:vector和map的差別，異同。空間分布，100萬資料存哪個比較合适。一、疊代器差別二、vector三、Map、Set四、vector_map 為什麼比map效率高五、如何選擇六、容器選擇原則七、效率對比

C++ 多線程用條件變量确定線程的執行順序而不是使用 sleep(1)

POJ 1284 Primitive Roots (歐拉函數&原根定理)

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

成員函數初始化清單

2021-08-13c++——類之操作符重載

swmm與lisflood-fp源碼如何一起編譯 CMake指令

Windows下VS開發環境環境安裝工程項目設定關于Debug和Release的提示

一文看懂字元串的加減乘除

C++ 第十五周報告1--《冒泡法排序》

C++實作簡單順序表

C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列二、優先級規律

線性表之順序表的實作

C++判斷素數、求最大公約數代碼判斷一個數是否為素數求兩個數的最大公約數

SequoiaDB巨杉資料庫C++驅動概述

劍指offer 刷題3

二十四 二叉樹中和為某一值的路徑3/2

二十六 二叉搜尋樹與雙向連結清單

三十八 二叉樹的深度

三十九 平衡二叉樹

五十八 二叉樹的下一個節點

對稱的二叉樹

二叉搜尋樹的第k個節點

按之字順序列印二叉樹3/3

二叉樹列印成多行

序列化二叉樹

繼續閱讀

二十四二叉樹中和為某一值的路徑3/2

二十六二叉搜尋樹與雙向連結清單

三十八二叉樹的深度

三十九平衡二叉樹

五十八二叉樹的下一個節點