二叉樹 LeetCode 刷題小結(jié)(二)

在上節(jié)的基礎(chǔ)上终蒂，本節(jié)我們將繼續(xù)匯總一些 LeetCode 有關(guān)二叉樹的題故响。

我們還是使用上節(jié)的程序框架宏蛉，可以手動輸入樣例并測試儿咱，解題的方法不唯一庭砍。
所有題均來自于leetcode。

翻轉(zhuǎn)二叉樹

翻轉(zhuǎn)一棵二叉樹混埠。

圖片.png

這個題需要我們翻轉(zhuǎn)二叉樹怠缸，可以用遞歸來實現(xiàn)。
當(dāng)一個節(jié)點為空钳宪，需不需要交換都無所謂凯旭；當(dāng)其不為空時，交換該節(jié)點的左右子樹即可使套，繼續(xù)遞歸其左右子樹，只要遍歷到每一個節(jié)點就可以了鞠柄，遍歷到該節(jié)點侦高，就換交換其左右子樹，以什么方式遍歷的其實無所謂厌杜。
簡單來說就是奉呛，每一個節(jié)點做好自己的事情：交換該節(jié)點的左右子樹计螺。每個節(jié)點做好這件事，再顧及到每個節(jié)點瞧壮，二叉樹就翻轉(zhuǎn)成功了登馒。

具體的程序如下：

//226 翻轉(zhuǎn)二叉樹
BiTree invertTree(BiTree root){
    if(root == NULL){
        return NULL;
    }
    BiTree r = invertTree(root->right);
    BiTree l = invertTree(root->left);

    root->left = r;
    root->right = l;
    return root;
}

測試程序：

int main(){
    // test
    //cout<<"test:......"<<endl;
    BiTree tree = levelCreate();
    tree = invertTree(tree);
    levelOrder(tree);
    return 0;
}

測試結(jié)果為：

4
2 7
1 3 6 9
# # # # # # # #
4 7 2 9 6 3 1

左葉子之和

計算給定二叉樹的所有左葉子之和。

圖片.png

這個題首先要明確什么是左葉子咆槽，節(jié)點為空陈轿，不操作，若一個節(jié)點是左葉子秦忿，取它的值相加麦射，之和明確什么時候遞歸左子樹，右子樹灯谣，這個問題就不難了潜秋。

具體程序：

// 404 左葉子之和
void sumOfLeftLeaves_helper(BiTree root,int& sum){
    if(root == NULL){
        sum = sum;
    }else{
        if(root->left != NULL){
            // 左葉子的條件
            if(root->left->left == NULL && root->left->right == NULL){
                sum += stoi(root->left->val);
            }else{
                sumOfLeftLeaves_helper(root->left,sum);
            }
            if(root->right != NULL){
                sumOfLeftLeaves_helper(root->right,sum);
            }
        }
    }
}
int sumOfLeftLeaves(BiTree root){
    int sum = 0;
    sumOfLeftLeaves_helper(root,sum);
    return sum;
}

測試程序：

int main(){
    // test
    //cout<<"test:......"<<endl;
    BiTree tree = levelCreate();
    cout<<sumOfLeftLeaves(tree)<<endl;
    return 0;
}

測試結(jié)果：

3 
9 20
# # 15 7
# # # #
24

二叉樹的中序遍歷

給定一個二叉樹，返回它的中序遍歷胎许。

圖片.png

這個峻呛，我在之前的博客《二叉樹常見操作的 C++ 實現(xiàn)(一)》，介紹過遞歸與非遞歸的前辜窑，中钩述，后序遍歷以及層次遍歷。
這里谬擦，我們再回顧一下吧切距。

遞歸版

遞歸版的很簡單。
具體程序如下：

// 94 二叉樹的中序遍歷,遞歸版
void inorderTraversal_helper(BiTree root,vector<int>& res){
    if(root == NULL){
        return ;
    }
    inorderTraversal_helper(root->left,res);
    res.push_back(stoi(root->val));
    inorderTraversal_helper(root->right,res);
}
vector<int> inorderTraversal(BiTree root){
    vector<int> res;
    inorderTraversal_helper(root,res);
    return res;
}

測試程序如下：

int main(){
    // test
    //cout<<"test:......"<<endl;
    BiTree tree = levelCreate();
    vector<int> res = inorderTraversal(tree);
    for(auto r : res){
        cout<<r<<" ";
    }
    cout<<endl;
    return 0;
}

測試結(jié)果：

1
# 2
3 #
# #
1 3 2

非遞歸版

具體程序如下：

// 94 二叉樹的中序遍歷,非遞歸版
vector<int> inorderTraversal_(BiTree root){
    stack<BiTree> m;
    vector<int> res;
    BiTree rt = root;
    while(rt != NULL|| m.size() != 0){
        while(rt != NULL){
            m.push(rt);
            rt = rt->left;
        }
        rt = m.top();
        m.pop();
        res.push_back(stoi(rt->val));
        rt = rt->right;
    }
    return res;
}

測試程序：

int main(){
    // test
    //cout<<"test:......"<<endl;
    BiTree tree = levelCreate();
    vector<int> res = inorderTraversal_(tree);
    for(auto r : res){
        cout<<r<<" ";
    }
    cout<<endl;
    return 0;
}

測試結(jié)果：

1
# 2
3 #
# #
1 3 2

驗證二叉搜索樹

給定一個二叉樹惨远，判斷其是否是一個有效的二叉搜索樹谜悟。

假設(shè)一個二叉搜索樹具有如下特征：
節(jié)點的左子樹只包含小于當(dāng)前節(jié)點的數(shù)。
節(jié)點的右子樹只包含大于當(dāng)前節(jié)點的數(shù)北秽。
所有左子樹和右子樹自身必須也是二叉搜索樹葡幸。

圖片.png

這個題可以使用遞歸，也可以使用非遞歸方法贺氓。

遞歸

具體程序如下：

// 98 驗證二叉搜索樹,遞歸
bool isValidBST_helper(BiTree root,long l,long r){
    if(root == NULL){
        return true;
    }
    if(l >= stoi(root->val) || r <= stoi(root->val)){
        return false;
    }
    if(isValidBST_helper(root->left,l,stoi(root->val)) && isValidBST_helper(root->right,stoi(root->val),r)){
        return true;
    }
    return false;
}
bool isValidBST(BiTree root){
    return isValidBST_helper(root,LONG_MIN,LONG_MAX);
}

測試程序：

int main(){
    // test
    //cout<<"test:......"<<endl;
    BiTree tree = levelCreate();
    cout<<isValidBST(tree)<<endl;
    return 0;
}

測試結(jié)果：

2
1 3
# # # #
1

5
1 4
# # 3 6
# # # #
0

非遞歸

具體程序如下：

// 98 驗證二叉搜索樹,非遞歸
bool isValidBST_(BiTree root){
    stack<BiTree> sk;
    long temp = LONG_MIN;
    while(root || sk.size()){
        while(root){
            sk.push(root);
            root = root->left;
        }
        root = sk.top();
        sk.pop();
        if(temp >= stoi(root->val)){
            return false;
        }
        temp = stoi(root->val);
        root = root->right;
    }
    return true;
}

測試程序：

int main(){
    // test
    //cout<<"test:......"<<endl;
    BiTree tree = levelCreate();
    cout<<isValidBST_(tree)<<endl;
    return 0;
}

測試結(jié)果為：

2
1 3
# # # #
1

5
1 4
# # 3 6
# # # #
0

二叉樹的層次遍歷

給定一個二叉樹蔚叨，返回其按層次遍歷的節(jié)點值。 （即逐層地辙培，從左到右訪問所有節(jié)點）蔑水。

圖片.png

二叉樹的層次遍歷在之前的博客中也是提到過的，這里我們再回顧一遍吧扬蕊。
關(guān)鍵點是用隊列保存每一層節(jié)點搀别，在本層節(jié)點數(shù)據(jù)域被保存后，用隊列保存下一層節(jié)點尾抑，直到遍歷完每一層歇父。

具體的程序如下：

// 102 二叉樹的層次遍歷,由于本題的代碼模板函數(shù)和原有的函數(shù)重復(fù)了,在原函數(shù)的基礎(chǔ)上增加了下劃線以區(qū)分
vector<vector<int>> levelOrder_(BiTree root){
    vector<vector<int>> res;
    queue<BiTree> q;
    if(root == NULL){
        return res;
    }
    q.push(root);
    while(!q.empty()){
        //蒂培， ，每一層的節(jié)點數(shù)
        int n = q.size();
        //用以存儲該層節(jié)點的數(shù)據(jù)域
        vector<int> level;
        while(n--){
            //以此將本層的節(jié)點出隊列
            BiTree node = q.front();
            q.pop();
            //存入level中
            level.push_back(stoi(node->val));
            if(node->left){
                q.push(node->left);
            }
            if(node->right){
                q.push(node->right);
            }
        }
        //保存該層所有節(jié)點
        res.push_back(level);
    }
    return res;
}

測試程序：

int main(){
    // test
    //cout<<"test:......"<<endl;
    BiTree tree = levelCreate();
    vector<vector<int>> res = levelOrder_(tree);
    for(auto r : res){
        for(auto _r : r){
            cout<<_r<<" ";
        }
        cout<<endl;
    }
    return 0;
}

測試結(jié)果為：

3
9 20
# # 15 7
# # # #
3
9 20
15 7

二叉樹的鋸齒形層次遍歷

給定一個二叉樹榜苫，返回其節(jié)點值的鋸齒形層次遍歷护戳。（即先從左往右，再從右往左進(jìn)行下一層遍歷垂睬，以此類推媳荒，層與層之間交替進(jìn)行）。

圖片.png

這個題和上一題很相似羔飞，但是有所不同肺樟，若根節(jié)點算第一層的話，奇數(shù)層是從左到右記錄的逻淌，偶數(shù)層是從右到左記錄的么伯。
那么我們使用一個棧是不夠的，需要有兩個棧卡儒，一個從左到右記錄田柔，一個從右到左記錄，先從左往右骨望，再從右往左進(jìn)行下一層遍歷硬爆，以此類推，層與層之間交替進(jìn)行擎鸠。直到兩個棧都為空了缀磕，遍歷完成。

具體程序如下：

// 103 二叉樹的鋸齒形層次遍歷
vector<vector<int>> zigzagLevelOrder(BiTree root){
    vector<vector<int>> res;
    if(root == NULL){
        return res;
    }
    //設(shè)置兩個棧劣光，一個從左到右記錄袜蚕，一個從右到左記錄
    //即先從左往右，再從右往左進(jìn)行下一層遍歷绢涡，以此類推牲剃，層與層之間交替進(jìn)行
    stack<BiTree> left_stack,right_stack;
    //奇數(shù)層，從左到右記錄,記錄完后將該層所有節(jié)點的左雄可，右子節(jié)點壓入右棧
    //偶數(shù)層凿傅，從右到左記錄,記錄完后將該層所有節(jié)點的右，左子節(jié)點壓入左棧
    left_stack.push(root);
    while(left_stack.size() != 0 || right_stack.size() != 0){
        if(left_stack.size() != 0){
            res.push_back(vector<int> ());
            while(left_stack.size() != 0){
                //得到當(dāng)前節(jié)點
                BiTree node = left_stack.top();
                left_stack.pop();
                res.back().push_back(stoi(node->val));
                //左節(jié)點壓入右棧
                if(node->left){
                    right_stack.push(node->left);
                }
                //右節(jié)點壓入右棧
                if(node->right){
                    right_stack.push(node->right);
                }
            }
        }
        if(right_stack.size() != 0){
            res.push_back(vector<int> ());
            while(right_stack.size() != 0){
                //得到當(dāng)前節(jié)點
                BiTree node = right_stack.top();
                right_stack.pop();
                res.back().push_back(stoi(node->val));
                //右節(jié)點壓入左棧
                if(node->right){
                    left_stack.push(node->right);
                }
                //左節(jié)點壓入左棧
                if(node->right){
                    left_stack.push(node->left);
                }
            }
        }
    }
    return res;
}

測試程序如下：

int main(){
    // test
    //cout<<"test:......"<<endl;
    BiTree tree = levelCreate();
    vector<vector<int>> res = zigzagLevelOrder(tree);
    for(auto r : res){
        for(auto _r : r){
            cout<<_r<<" ";
        }
        cout<<endl;
    }
    return 0;
}

測試結(jié)果如下：

3
9 20
# # 15 7
# # # #
3
20 9
15 7

全部代碼見 github 数苫，main.cpp 中不帶測試程序聪舒。
本節(jié)內(nèi)容到此結(jié)束，之后將繼續(xù)更新虐急。

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 人面猴
    序言：七十年代末过椎，一起剝皮案震驚了整個濱河市，隨后出現(xiàn)的幾起案子戏仓，更是在濱河造成了極大的恐慌疚宇，老刑警劉巖，帶你破解...
    沈念sama閱讀 217,542評論 6贊 504
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件赏殃，死亡現(xiàn)場離奇詭異敷待，居然都是意外死亡，警方通過查閱死者的電腦和手機仁热，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,822評論 3贊 394
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進(jìn)店門榜揖，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人抗蠢，你說我怎么就攤上這事举哟。” “怎么了迅矛？”我有些...
    開封第一講書人閱讀 163,912評論 0贊 354
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵妨猩，是天一觀的道長。 經(jīng)常有香客問我秽褒，道長壶硅，這世上最難降的妖魔是什么？ 我笑而不...
    開封第一講書人閱讀 58,449評論 1贊 293
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任销斟，我火速辦了婚禮庐椒，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘蚂踊。我一直安慰自己约谈，他們只是感情好，可當(dāng)我...
    茶點故事閱讀 67,500評論 6贊 392
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布犁钟。 她就那樣靜靜地躺著棱诱，像睡著了一般。 火紅的嫁衣襯著肌膚如雪特纤。 梳的紋絲不亂的頭發(fā)上军俊，一...
    開封第一講書人閱讀 51,370評論 1贊 302
  • 城市分裂傳說
    那天，我揣著相機與錄音捧存，去河邊找鬼粪躬。 笑死，一個胖子當(dāng)著我的面吹牛昔穴，可吹牛的內(nèi)容都是我干的镰官。 我是一名探鬼主播，決...
    沈念sama閱讀 40,193評論 3贊 418
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼吗货，長吁一口氣：“原來是場噩夢啊……” “哼泳唠！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起宙搬，我...
    開封第一講書人閱讀 39,074評論 0贊 276
  • 萬榮殺人案實錄
    序言：老撾萬榮一對情侶失蹤笨腥，失蹤者是張志新（化名）和其女友劉穎拓哺，沒想到半個月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體脖母，經(jīng)...
    沈念sama閱讀 45,505評論 1贊 314
  • ?護(hù)林員之死
    正文 獨居荒郊野嶺守林人離奇死亡士鸥，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 37,722評論 3贊 335
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年，在試婚紗的時候發(fā)現(xiàn)自己被綠了谆级。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片烤礁。...
    茶點故事閱讀 39,841評論 1贊 348
  • 活死人
    序言：一個原本活蹦亂跳的男人離奇死亡，死狀恐怖肥照，靈堂內(nèi)的尸體忽然破棺而出脚仔，到底是詐尸還是另有隱情，我是刑警寧澤舆绎，帶...
    沈念sama閱讀 35,569評論 5贊 345
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布鲤脏，位于F島的核電站，受9級特大地震影響亿蒸，放射性物質(zhì)發(fā)生泄漏凑兰。R本人自食惡果不足惜，卻給世界環(huán)境...
    茶點故事閱讀 41,168評論 3贊 328
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一边锁、第九天 我趴在偏房一處隱蔽的房頂上張望姑食。 院中可真熱鬧，春花似錦茅坛、人聲如沸音半。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,783評論 0贊 22
  • 一樁弒父案贡蓖，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽曹鸠。三九已至，卻和暖如春斥铺，著一層夾襖步出監(jiān)牢的瞬間彻桃，已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 32,918評論 1贊 269
  • 情欲美人皮
    我被黑心中介騙來泰國打工晾蜘， 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留邻眷，地道東北人。 一個月前我還...
    沈念sama閱讀 47,962評論 2贊 370
  • 代替公主和親
    正文 我出身青樓剔交，卻偏偏與公主長得像肆饶，于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子岖常，可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 44,781評論 2贊 354