代碼隨想錄筆記--二叉樹篇

這篇具有很好參考價值的文章主要介紹了代碼隨想錄筆記--二叉樹篇。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

1--遞歸遍歷

1-1--前序遍歷

1-2--中序遍歷

1-3--后序遍歷

2--迭代遍歷

2-1--前序遍歷

2-2--后序遍歷

2-3--中序遍歷

3--二叉樹的層序遍歷

4--翻轉二叉樹

5--對稱二叉樹

6--二叉樹最大深度

7--二叉樹的最小深度

8--完全二叉樹節(jié)點的數(shù)量

9--平衡二叉樹

10--二叉樹的所有路徑

11--左葉子之和

12--找樹左下角的值

13--路徑總和

14--從中序與后序遍歷序列構造二叉樹

15--最大二叉樹

16--合并二叉樹

17--二叉搜索樹中的搜索

18--驗證二叉搜索樹

19--二叉搜索樹的最小絕對差

20--二叉搜索樹中的眾數(shù)

21--二叉樹的最近公共祖先

22--二叉搜索樹的最近公共祖先

23--二叉搜索樹中的插入操作

24--刪除二叉搜索樹中的節(jié)點

25--修建二叉搜索樹

26--將有序數(shù)組轉換為二叉搜索樹

27--把二叉搜索樹轉換為累加樹

1--遞歸遍歷

1-1--前序遍歷

代碼隨想錄筆記--二叉樹篇,數(shù)據(jù)結構&LeetCode,數(shù)據(jù)結構

前序遍歷：根→左→右；

#include <iostream>
#include <vector>

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:
    std::vector<int> preorderTraversal(TreeNode* root) {
        std::vector<int> res;
        dfs(root, res);
        return res;
    }

    void dfs(TreeNode* root, std::vector<int>& res){
        if(root == nullptr) return;
        res.push_back(root->val);
        dfs(root->left, res);
        dfs(root->right, res);
    }
};

int main(int argc, char* argv[]){
    // root = [1, null, 2, 3]
    TreeNode *Node1 = new TreeNode(1);
    TreeNode *Node2 = new TreeNode(2);
    TreeNode *Node3 = new TreeNode(3);
    Node1->right = Node2;
    Node2->left = Node3;

    Solution S1;
    std::vector<int> res = S1.preorderTraversal(Node1);
    for(auto item : res) std::cout << item << " ";
    std::cout << std::endl;
    return 0;
}

1-2--中序遍歷

代碼隨想錄筆記--二叉樹篇,數(shù)據(jù)結構&LeetCode,數(shù)據(jù)結構

中序遍歷：左→根→右；

#include <iostream>
#include <vector>

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:
    std::vector<int> inorderTraversal(TreeNode* root) {
        std::vector<int> res;
        dfs(root, res);
        return res;
    }

    void dfs(TreeNode* root, std::vector<int>& res){
        if(root == nullptr) return;
        dfs(root->left, res);
        res.push_back(root->val);
        dfs(root->right, res);
    }
};

int main(int argc, char* argv[]){
    // root = [1, null, 2, 3]
    TreeNode *Node1 = new TreeNode(1);
    TreeNode *Node2 = new TreeNode(2);
    TreeNode *Node3 = new TreeNode(3);
    Node1->right = Node2;
    Node2->left = Node3;

    Solution S1;
    std::vector<int> res = S1.inorderTraversal(Node1);
    for(auto item : res) std::cout << item << " ";
    std::cout << std::endl;
    return 0;
}

1-3--后序遍歷

代碼隨想錄筆記--二叉樹篇,數(shù)據(jù)結構&LeetCode,數(shù)據(jù)結構

后序遍歷：左→右→根；

#include <iostream>
#include <vector>

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:
    std::vector<int> postorderTraversal(TreeNode* root) {
        std::vector<int> res;
        dfs(root, res);
        return res;
    }

    void dfs(TreeNode* root, std::vector<int>& res){
        if(root == nullptr) return;
        dfs(root->left, res);
        dfs(root->right, res);
        res.push_back(root->val);
    }
};

int main(int argc, char* argv[]){
    // root = [1, null, 2, 3]
    TreeNode *Node1 = new TreeNode(1);
    TreeNode *Node2 = new TreeNode(2);
    TreeNode *Node3 = new TreeNode(3);
    Node1->right = Node2;
    Node2->left = Node3;

    Solution S1;
    std::vector<int> res = S1.postorderTraversal(Node1);
    for(auto item : res) std::cout << item << " ";
    std::cout << std::endl;
    return 0;
}

2--迭代遍歷

2-1--前序遍歷

????????基于棧結構，先將根節(jié)點入棧，再將節(jié)點從棧中彈出，如果節(jié)點的右孩子不為空，則右孩子入棧；如果節(jié)點的左孩子不為空，則左孩子入棧；

? ? ? ? 循環(huán)出棧處理節(jié)點，并將右孩子和左孩子存在棧中（右孩子先進棧，左孩子再進棧，因為棧先進后出，這樣可以確保左孩子先出棧，符合根→左→右的順序）；

#include <iostream>
#include <vector>
#include <stack>

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:
    std::vector<int> preorderTraversal(TreeNode* root) {
        std::vector<int> res;
        if(root == nullptr) return res;
        std::stack<TreeNode*> stk;
        stk.push(root);
        while(!stk.empty()){
            TreeNode *tmp = stk.top();
            stk.pop();
            res.push_back(tmp->val);
            if(tmp->right != nullptr) stk.push(tmp->right); // 右
            if(tmp->left != nullptr) stk.push(tmp->left); // 左
        }
        return res;
    }
};

int main(int argc, char* argv[]){
    // root = [1, null, 2, 3]
    TreeNode *Node1 = new TreeNode(1);
    TreeNode *Node2 = new TreeNode(2);
    TreeNode *Node3 = new TreeNode(3);
    Node1->right = Node2;
    Node2->left = Node3;

    Solution S1;
    std::vector<int> res = S1.preorderTraversal(Node1);
    for(auto item : res) std::cout << item << " ";
    std::cout << std::endl;
    return 0;
}

2-2--后序遍歷

? ? ? ? 可以使用兩個棧來實現(xiàn)，一個是遍歷棧，一個是收集棧，參考之前的筆記：后序遍歷的迭代實現(xiàn)? ? ? ??

? ? ? ? 也可以類似于前序遍歷，基于一個棧實現(xiàn)，只不過需要改變入棧順序：每出棧處理一個節(jié)點，其左孩子入棧，再右孩子入棧；此時處理順序為：根->右->左，最后將結果 reverse 即可；

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

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:
    std::vector<int> postorderTraversal(TreeNode* root) {
        std::vector<int> res;
        if(root == nullptr) return res;
        std::stack<TreeNode*> stk;
        stk.push(root);
        while(!stk.empty()){
            TreeNode* tmp = stk.top();
            stk.pop();
            if(tmp->left != nullptr) stk.push(tmp->left);
            if(tmp->right != nullptr) stk.push(tmp->right);
            res.push_back(tmp->val);
        }
        // 反轉
        std::reverse(res.begin(), res.end());
        return res;
    }
};

int main(int argc, char* argv[]){
    // root = [1, null, 2, 3]
    TreeNode *Node1 = new TreeNode(1);
    TreeNode *Node2 = new TreeNode(2);
    TreeNode *Node3 = new TreeNode(3);
    Node1->right = Node2;
    Node2->left = Node3;

    Solution S1;
    std::vector<int> res = S1.postorderTraversal(Node1);
    for(auto item : res) std::cout << item << " ";
    std::cout << std::endl;
    return 0;
}

2-3--中序遍歷

基于棧結構，初始化一個棧，根節(jié)點入棧；

????????①：左子結點全部入棧；

? ? ? ? ②：結點出棧，處理結點；

????????③：對出棧結點的右子樹重復執(zhí)行第 ① 步操作；

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

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:
    std::vector<int> inorderTraversal(TreeNode* root) {
        std::vector<int> res;
        if(root == nullptr) return res;
        std::stack<TreeNode*> stk;
        while(!stk.empty() || root != nullptr){
            if(root != nullptr){ // 左子結點全部入棧
                stk.push(root);
                root = root->left;
            }
            else{
                TreeNode *tmp = stk.top();
                stk.pop();
                res.push_back(tmp->val);
                // 出棧節(jié)點的右孩子執(zhí)行相同操作
                root = tmp->right;
            }    
        }
        return res;
    }
};

int main(int argc, char* argv[]){
    // root = [1, null, 2, 3]
    TreeNode *Node1 = new TreeNode(1);
    TreeNode *Node2 = new TreeNode(2);
    TreeNode *Node3 = new TreeNode(3);
    Node1->right = Node2;
    Node2->left = Node3;

    Solution S1;
    std::vector<int> res = S1.inorderTraversal(Node1);
    for(auto item : res) std::cout << item << " ";
    std::cout << std::endl;
    return 0;
}

3--二叉樹的層序遍歷

代碼隨想錄筆記--二叉樹篇,數(shù)據(jù)結構&LeetCode,數(shù)據(jù)結構

主要思路：

? ? ? ? 經(jīng)典廣度優(yōu)先搜索，基于隊列；

????????對于本題需要將同一層的節(jié)點放在一個數(shù)組中，因此遍歷的時候需要用一個變量 nums 來記錄當前層的節(jié)點數(shù)，即 nums 等于隊列元素的數(shù)目；

#include <iostream>
#include <vector>
#include <queue>

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:
    std::vector<std::vector<int>> levelOrder(TreeNode* root) {
        std::vector<std::vector<int>> res;
        if(root == nullptr) return res;
        std::queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            int nums = q.size(); // 當前層的節(jié)點數(shù)
            std::vector<int> tmp;
            while(nums > 0){ // 遍歷處理同一層
                TreeNode *cur = q.front();
                q.pop();
                tmp.push_back(cur->val);

                if(cur->left != nullptr) q.push(cur->left);
                if(cur->right != nullptr) q.push(cur->right);
                
                nums--;
            }
            res.push_back(tmp); // 記錄當前層的元素
        }
        return res;
    }
};

int main(int argc, char* argv[]){
    // root = [1, null, 2, 3]
    TreeNode *Node1 = new TreeNode(3);
    TreeNode *Node2 = new TreeNode(9);
    TreeNode *Node3 = new TreeNode(20);
    TreeNode *Node4 = new TreeNode(15);
    TreeNode *Node5 = new TreeNode(7);
    Node1->left = Node2;
    Node1->right = Node3;
    Node3->left = Node4;
    Node3->right = Node5;

    Solution S1;
    std::vector<std::vector<int>> res = S1.levelOrder(Node1);
    for(auto item : res) {
        for (int v : item) std::cout << v << " ";
        std::cout << std::endl;
    }
    return 0;
}

4--翻轉二叉樹

代碼隨想錄筆記--二叉樹篇,數(shù)據(jù)結構&LeetCode,數(shù)據(jù)結構

主要思路：

? ? ? ? 遞歸交換左右子樹；

#include <iostream>
#include <vector>
#include <queue>

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* invertTree(TreeNode* root) {
        reverse(root);
        return root;
    }
    void reverse(TreeNode *root){
        if(root == nullptr) return;
        reverse(root->left);
        reverse(root->right);
        TreeNode *tmp = root->left;
        root->left = root->right;
        root->right = tmp;
    }
};

// 層次遍歷打印
void PrintTree(TreeNode *root){
    std::queue<TreeNode*> q;
    q.push(root);
    while(!q.empty()) {
        TreeNode *tmp = q.front();
        q.pop();
        std::cout << tmp->val << " ";
        if(tmp->left != nullptr) q.push(tmp->left);
        if(tmp->right != nullptr) q.push(tmp->right);
    }
}

int main(int argc, char* argv[]){
    // root = [4,2,7,1,3,6,9]
    TreeNode *Node1 = new TreeNode(4);
    TreeNode *Node2 = new TreeNode(2);
    TreeNode *Node3 = new TreeNode(7);
    TreeNode *Node4 = new TreeNode(1);
    TreeNode *Node5 = new TreeNode(3);
    TreeNode *Node6 = new TreeNode(6);
    TreeNode *Node7 = new TreeNode(9);

    Node1->left = Node2;
    Node1->right = Node3;
    Node2->left = Node4;
    Node2->right = Node5;
    Node3->left = Node6;
    Node3->right = Node7;

    Solution S1;
    TreeNode *res = S1.invertTree(Node1);
    PrintTree(res);
}

5--對稱二叉樹

代碼隨想錄筆記--二叉樹篇,數(shù)據(jù)結構&LeetCode,數(shù)據(jù)結構

主要思路：

????????遞歸判斷左樹的左子樹是否與右數(shù)的右子樹相等，左樹的右子樹是否與右樹的左子樹相等；

#include <iostream>
#include <vector>
#include <queue>

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:
    bool isSymmetric(TreeNode* root) {
        if(root == nullptr) return true;
        bool res = dfs(root->left, root->right);
        return res;
    }
    bool dfs(TreeNode *left, TreeNode *right){
        if((left != nullptr && right == nullptr) ||
        (left == nullptr && right != nullptr)) return false;

        if(left == nullptr && right == nullptr) return true;
        if (left->val != right->val) return false;

        bool isSame1 = dfs(left->left, right->right);
        bool isSame2 = dfs(left->right, right->left);
        return isSame1 && isSame2;
    }
};

int main(int argc, char* argv[]){
    // root = [4,2,7,1,3,6,9]
    TreeNode *Node1 = new TreeNode(1);
    TreeNode *Node2 = new TreeNode(2);
    TreeNode *Node3 = new TreeNode(2);
    TreeNode *Node4 = new TreeNode(3);
    TreeNode *Node5 = new TreeNode(4);
    TreeNode *Node6 = new TreeNode(4);
    TreeNode *Node7 = new TreeNode(3);

    Node1->left = Node2;
    Node1->right = Node3;
    Node2->left = Node4;
    Node2->right = Node5;
    Node3->left = Node6;
    Node3->right = Node7;

    Solution S1;
    bool res = S1.isSymmetric(Node1);
    if(res) std::cout << "true" << std::endl;
    else std::cout << "false" << std::endl;
}

6--二叉樹最大深度

代碼隨想錄筆記--二叉樹篇,數(shù)據(jù)結構&LeetCode,數(shù)據(jù)結構

主要思路：

? ? ? ? 遞歸計算左右子樹的深度，選取兩者最大值 +1 返回；

#include <iostream>
#include <vector>
#include <queue>

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:
    int maxDepth(TreeNode* root) {
        if(root == nullptr) return 0;
        int res = dfs(root);
        return res;
    }

    int dfs(TreeNode* root){
        if(root == nullptr) return 0;
        int left_height = dfs(root->left);
        int right_height = dfs(root->right);
        int cur_height = std::max(left_height, right_height) + 1;
        return cur_height;
    }
};

int main(int argc, char* argv[]){
    // root = [3,9,20,null,null,15,7]
    TreeNode *Node1 = new TreeNode(3);
    TreeNode *Node2 = new TreeNode(9);
    TreeNode *Node3 = new TreeNode(20);
    TreeNode *Node4 = new TreeNode(15);
    TreeNode *Node5 = new TreeNode(7);

    Node1->left = Node2;
    Node1->right = Node3;
    Node3->left = Node4;
    Node3->right = Node5;

    Solution S1;
    int res = S1.maxDepth(Node1);
    std::cout << res << std::endl;
    return 0;
}

7--二叉樹的最小深度

代碼隨想錄筆記--二叉樹篇,數(shù)據(jù)結構&LeetCode,數(shù)據(jù)結構

主要思路：

? ? ? ? 與上題有點類似，遞歸返回最小深度即可，但需要剔除根節(jié)點一個子樹為空的情況；

? ? ? ? 對于一個根節(jié)點，其中一個子樹為空，則其最小深度是不為空的子樹的深度；

#include <iostream>
#include <vector>
#include <queue>

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:
    int minDepth(TreeNode* root) {
        if(root == nullptr) return 0;
        return dfs(root);
    }

    int dfs(TreeNode *root){
        if(root == nullptr) return 0;
        // 剔除兩種情況
        if(root->left == nullptr) return dfs(root->right) + 1;
        else if(root->right == nullptr) return dfs(root->left) + 1;
        else{
            int left_height = dfs(root->left);
            int right_height = dfs(root->right);
            int cur_min_height = std::min(left_height, right_height) + 1;
            return cur_min_height;
        }
    }
};

int main(int argc, char* argv[]){
    // root = [3,9,20,null,null,15,7]
    TreeNode *Node1 = new TreeNode(3);
    TreeNode *Node2 = new TreeNode(9);
    TreeNode *Node3 = new TreeNode(20);
    TreeNode *Node4 = new TreeNode(15);
    TreeNode *Node5 = new TreeNode(7);

    Node1->left = Node2;
    Node1->right = Node3;
    Node3->left = Node4;
    Node3->right = Node5;

    Solution S1;
    int res = S1.minDepth(Node1);
    std::cout << res << std::endl;
    return 0;
}

8--完全二叉樹節(jié)點的數(shù)量

代碼隨想錄筆記--二叉樹篇,數(shù)據(jù)結構&LeetCode,數(shù)據(jù)結構

主要思路：

? ? ? ? 普通二叉樹可以通過層次遍歷來統(tǒng)計節(jié)點數(shù)目；

? ? ? ? 對于本題中的完全二叉樹，可以通過 2**k - 1 的公式來計算二叉樹節(jié)點的數(shù)目；

? ? ? ? 首先需判斷一個子樹是否為完全二叉樹，如果是則通過上式計算；如果不是完全二叉樹，則對于當前子樹，需要分別向左右子樹遞歸計算其節(jié)點數(shù)目（相當于獲取信息），最后將結果相加（相當于處理信息），并加上1返回即可；

#include <iostream>
#include <vector>
#include <queue>

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:
    int countNodes(TreeNode* root) {
        if(root == nullptr) return 0;
        return dfs(root);
    }
    int dfs(TreeNode *root){
        if(root == nullptr) return 0;
        TreeNode *left = root->left, *right = root->right;
        int left_height = 0, right_height = 0;
        while(left != nullptr){
            left = left->left;
            left_height++;
        }
        while(right != nullptr){
            right = right->right;
            right_height++;
        }
        if(left_height == right_height) return (2<<left_height) - 1; // 滿二叉樹
        int left_nums = dfs(root->left);
        int right_nums = dfs(root->right);
        return left_nums + right_nums + 1;
    }
};

int main(int argc, char* argv[]){
    // root = [1,2,3,4,5,6]
    TreeNode *Node1 = new TreeNode(1);
    TreeNode *Node2 = new TreeNode(2);
    TreeNode *Node3 = new TreeNode(3);
    TreeNode *Node4 = new TreeNode(4);
    TreeNode *Node5 = new TreeNode(5);
    TreeNode *Node6 = new TreeNode(6);

    Node1->left = Node2;
    Node1->right = Node3;
    Node2->left = Node4;
    Node2->right = Node5;
    Node3->left = Node6;

    Solution S1;
    int res = S1.countNodes(Node1);
    std::cout << res << std::endl;
    return 0;
}

9--平衡二叉樹

代碼隨想錄筆記--二叉樹篇,數(shù)據(jù)結構&LeetCode,數(shù)據(jù)結構

主要思路：

? ? ? ? 通過高度差不大于1，來遞歸判斷子樹是否是平衡二叉樹，不是則返回-1，是則返回對應的高度；

#include <iostream>
#include <vector>

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:
    bool isBalanced(TreeNode* root) {
        if(root == nullptr) return true;
        int height = dfs(root);
        return height == -1 ? false : true;
    }

    int dfs(TreeNode *root){
        if(root == nullptr) return 0;
        int left_height = dfs(root->left);
        if(left_height == -1) return -1;
        int right_height = dfs(root->right);
        if(right_height == -1) return -1;
        if(std::abs(left_height - right_height) > 1) return -1;
        else return std::max(left_height, right_height) + 1;
    }
};

int main(int argc, char* argv[]){
    // root = [3,9,20,null,null,15,7]
    TreeNode *Node1 = new TreeNode(3);
    TreeNode *Node2 = new TreeNode(9);
    TreeNode *Node3 = new TreeNode(20);
    TreeNode *Node4 = new TreeNode(15);
    TreeNode *Node5 = new TreeNode(7);

    Node1->left = Node2;
    Node1->right = Node3;
    Node3->left = Node4;
    Node3->right = Node5;

    Solution S1;
    bool res = S1.isBalanced(Node1);
    if(res) std::cout << "true" << std::endl;
    else std::cout << "false" << std::endl;
    return 0;
}

10--二叉樹的所有路徑

代碼隨想錄筆記--二叉樹篇,數(shù)據(jù)結構&LeetCode,數(shù)據(jù)結構

主要思路：

? ? ? ? 遞歸記錄路徑；

#include <iostream>
#include <vector>
#include <string>

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:
    std::vector<std::string> binaryTreePaths(TreeNode* root) {
        std::vector<std::string> res;
        if(root == nullptr) return res;
        std::string path = "";
        dfs(root, res, path);
        return res;
    }

    void dfs(TreeNode *root, std::vector<std::string>& res, std::string path){
        if(root == nullptr) return;

        path += std::to_string(root->val);
        if(root->left == nullptr && root->right == nullptr) { // 葉子節(jié)點，回收路徑
            res.push_back(path);
            return;
        }
        else path += "->";
        dfs(root->left, res, path);
        dfs(root->right, res, path);
    }
};

int main(int argc, char* argv[]){
    // root = [1,2,3,null,5]
    TreeNode *Node1 = new TreeNode(1);
    TreeNode *Node2 = new TreeNode(2);
    TreeNode *Node3 = new TreeNode(3);
    TreeNode *Node4 = new TreeNode(5);

    Node1->left = Node2;
    Node1->right = Node3;
    Node2->right = Node4;

    Solution S1;
    std::vector<std::string> res = S1.binaryTreePaths(Node1);
    for(auto path : res) std::cout << path << std::endl;
    return 0;
}

11--左葉子之和

代碼隨想錄筆記--二叉樹篇,數(shù)據(jù)結構&LeetCode,數(shù)據(jù)結構

主要思路：

? ? ? ? 遞歸到葉子節(jié)點的上一層，返回其左葉子之和；

#include <iostream>
#include <vector>
#include <string>

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:
    int sumOfLeftLeaves(TreeNode* root) {
        if(root == nullptr) return 0;
        return dfs(root);
    }
    int dfs(TreeNode* root){
        if(root == nullptr) return 0;
        if(root->left == nullptr && root->right == nullptr) return 0;
        int sum = 0;
        if(root->left != nullptr && root->left->left == nullptr && root->left->right == nullptr){
            sum = root->left->val;
        }
        int left = dfs(root->left);
        int right = dfs(root->right);
        return left + right + sum;
    }
};

int main(int argc, char* argv[]){
    // root = [3,9,20,null,null,15,7]
    TreeNode *Node1 = new TreeNode(3);
    TreeNode *Node2 = new TreeNode(9);
    TreeNode *Node3 = new TreeNode(20);
    TreeNode *Node4 = new TreeNode(15);
    TreeNode *Node5 = new TreeNode(7);

    Node1->left = Node2;
    Node1->right = Node3;
    Node3->left = Node4;
    Node3->right = Node5;

    Solution S1;
    int res = S1.sumOfLeftLeaves(Node1);
    std::cout << res << std::endl;
    return 0;
}

12--找樹左下角的值

代碼隨想錄筆記--二叉樹篇,數(shù)據(jù)結構&LeetCode,數(shù)據(jù)結構

主要思路：

? ? ? ? 遞歸到最大深度層，優(yōu)先返回最左邊的節(jié)點值，即遞歸時優(yōu)先搜索左子樹；

#include <iostream>
#include <vector>
#include <limits.h>

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:
    int findBottomLeftValue(TreeNode* root) {
        if(root == nullptr) return 0;
        int max_height = INT_MIN;
        int result = 0;
        dfs(root, 0, max_height, result);
        return result;
    }

    void dfs(TreeNode* root, int curheight, int& max_height, int& res){
        if(root == nullptr) return;
        if(root->left == nullptr && root->right == nullptr){ // 葉子節(jié)點
            if(curheight + 1 > max_height){
                max_height = curheight + 1;
                res = root->val;
                return;
            }
        }
        dfs(root->left, curheight+1, max_height, res);
        dfs(root->right, curheight+1, max_height, res);  
    }
};

int main(int argc, char* argv[]){
    // root = [3,9,20,null,null,15,7]
    TreeNode *Node1 = new TreeNode(2);
    TreeNode *Node2 = new TreeNode(1);
    TreeNode *Node3 = new TreeNode(3);

    Node1->left = Node2;
    Node1->right = Node3;

    Solution S1;
    int res = S1.findBottomLeftValue(Node1);
    std::cout << res << std::endl;
    return 0;
}

13--路徑總和

代碼隨想錄筆記--二叉樹篇,數(shù)據(jù)結構&LeetCode,數(shù)據(jù)結構

主要思路：

? ? ? ? 遞歸搜索，判斷路徑和是否等于目標值即可；

#include <iostream>
#include <vector>
#include <limits.h>

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:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(root == nullptr) return false;
        return dfs(root, targetSum);
    }

    bool dfs(TreeNode* root, int targetSum){
        if(root == nullptr) return false;
        if(root->left == nullptr && root->right == nullptr && targetSum == root->val){
            return true;
        }
        bool left = dfs(root->left, targetSum - root->val);
        if(left) return true;
        bool right = dfs(root->right, targetSum - root->val);
        if(right) return true;

        return false;
    }
};

int main(int argc, char* argv[]){
    // root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
    TreeNode *Node1 = new TreeNode(5);
    TreeNode *Node2 = new TreeNode(4);
    TreeNode *Node3 = new TreeNode(8);
    TreeNode *Node4 = new TreeNode(11);
    TreeNode *Node5 = new TreeNode(13);
    TreeNode *Node6 = new TreeNode(4);
    TreeNode *Node7 = new TreeNode(7);
    TreeNode *Node8 = new TreeNode(2);
    TreeNode *Node9 = new TreeNode(1);

    Node1->left = Node2;
    Node1->right = Node3;
    Node2->left = Node4;
    Node3->left = Node5;
    Node3->right = Node6;
    Node4->left = Node7;
    Node4->right = Node8;
    Node6->right = Node9;

    int target = 22;

    Solution S1;
    bool res = S1.hasPathSum(Node1, target);
    if(res) std::cout << "True" << std::endl;
    else std::cout << "false" << std::endl;
    return 0;
}

14--從中序與后序遍歷序列構造二叉樹

代碼隨想錄筆記--二叉樹篇,數(shù)據(jù)結構&LeetCode,數(shù)據(jù)結構

主要思路：

????????中序遍歷的順序為：左→根→右，后序遍歷的順序為：左→右→根；即后序遍歷的最后一個節(jié)點是根節(jié)點，因此可以根據(jù)根節(jié)點來劃分中序遍歷，將其劃分為左子樹和右子樹，再根據(jù)左右子樹的大小來劃分后序遍歷，遞歸構建二叉樹；

#include <iostream>
#include <vector>
#include <queue>

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(std::vector<int>& inorder, std::vector<int>& postorder) {
        TreeNode *root = dfs(inorder, postorder);
        return root;
    }

    TreeNode* dfs(std::vector<int>& inorder, std::vector<int>& postorder){
        if(postorder.size() == 0) return nullptr;
        TreeNode *root = new TreeNode(postorder[postorder.size() - 1]); // 根節(jié)點
        if(postorder.size() == 1) return root;

        // 劃分中序遍歷
        int idx;
        for(idx = 0; idx < inorder.size(); idx++){
            if(inorder[idx] == root->val) break; // 找到中序遍歷的根節(jié)點
        }
        // 劃分后序遍歷
        std::vector<int> left_inorder(inorder.begin(), inorder.begin()+idx); // 左子樹的中序
        std::vector<int> right_inorder(inorder.begin()+idx+1, inorder.end()); // 右子樹的中序
        std::vector<int> left_postorder(postorder.begin(), postorder.begin() + left_inorder.size()); // 左子樹的后序
        std::vector<int> right_postorder(postorder.begin() + left_inorder.size(), postorder.end() - 1); // 右子樹的后序
        root->left = dfs(left_inorder, left_postorder);
        root->right = dfs(right_inorder, right_postorder);
        return root;
    }
};

int main(int argc, char* argv[]){
    // inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
    std::vector<int> inorder = {9, 3, 15, 20, 7};
    std::vector<int> postorder = {9, 15, 7, 20, 3};
    Solution S1;
    TreeNode *root = S1.buildTree(inorder, postorder);
    // 層次遍歷
    std::queue<TreeNode*> q;
    q.push(root);
    while(!q.empty()){
        TreeNode *tmp = q.front();
        q.pop();
        std::cout << tmp->val << " ";
        if(tmp->left != nullptr) q.push(tmp->left);
        if(tmp->right != nullptr) q.push(tmp->right);
    }
    std::cout << std::endl;
    return 0;
}

15--最大二叉樹

代碼隨想錄筆記--二叉樹篇,數(shù)據(jù)結構&LeetCode,數(shù)據(jù)結構

主要思路：

? ? ? ? 遞歸構建二叉樹，首先尋找數(shù)組中的最大值，根據(jù)最大值劃分左子樹和右子樹，遞歸構建左子樹和右子樹；

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>

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* constructMaximumBinaryTree(std::vector<int>& nums) {
        TreeNode *root = dfs(nums);
        return root;
    }
    TreeNode* dfs(std::vector<int>& nums){
        if(nums.size() == 1){
            TreeNode* root = new TreeNode(nums[0]);
            return root;
        }
        // 遍歷尋找最大值
        int max_idx = 0, max_value = INT_MIN;
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] > max_value) {
                max_value = nums[i];
                max_idx = i;
            }
        }
        TreeNode *root = new TreeNode(nums[max_idx]);
        if(max_idx > 0){
            std::vector<int> left_nums(nums.begin(), nums.begin() + max_idx);
            root->left = dfs(left_nums);
        }
        if(max_idx < nums.size() - 1){
            std::vector<int> right_nums(nums.begin() + max_idx + 1, nums.end());
            root->right = dfs(right_nums);
        }
        return root;
    }
};

int main(int argc, char* argv[]){
    // nums = [3,2,1,6,0,5]
    std::vector<int> nums = {3, 2, 1, 6, 0, 5};
    Solution S1;
    TreeNode *root = S1.constructMaximumBinaryTree(nums);
    // 層次遍歷
    std::queue<TreeNode*> q;
    q.push(root);
    while(!q.empty()){
        TreeNode *tmp = q.front();
        q.pop();
        std::cout << tmp->val << " ";
        if(tmp->left != nullptr) q.push(tmp->left);
        if(tmp->right != nullptr) q.push(tmp->right);
    }
    std::cout << std::endl;
    return 0;
}

16--合并二叉樹

代碼隨想錄筆記--二叉樹篇,數(shù)據(jù)結構&LeetCode,數(shù)據(jù)結構

主要思路：

? ? ? ? 遞歸構建二叉樹，兩顆子樹均不為 null 時，則構建新節(jié)點，其值為傳入的兩根節(jié)點之和；

? ? ? ? 當其中一顆子樹為空時，返回另一顆子樹；

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>

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* mergeTrees(TreeNode* root1, TreeNode* root2) {
        return dfs(root1, root2);
    }

    TreeNode* dfs(TreeNode* root1, TreeNode* root2){
        if(root1 == nullptr) return root2;
        if(root2 == nullptr) return root1;
        TreeNode *root = new TreeNode(root1->val + root2->val);
        root->left = dfs(root1->left, root2->left);
        root->right = dfs(root1->right, root2->right);
        return root;
    }    
};

int main(int argc, char* argv[]){
    // root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
    TreeNode* Node1_1 = new TreeNode(1);
    TreeNode* Node1_2 = new TreeNode(3);
    TreeNode* Node1_3 = new TreeNode(2);
    TreeNode* Node1_4 = new TreeNode(5);

    Node1_1->left = Node1_2;
    Node1_1->right = Node1_3;
    Node1_2->left = Node1_4;

    TreeNode* Node2_1 = new TreeNode(2);
    TreeNode* Node2_2 = new TreeNode(1);
    TreeNode* Node2_3 = new TreeNode(3);
    TreeNode* Node2_4 = new TreeNode(4);
    TreeNode* Node2_5 = new TreeNode(7);

    Node2_1->left = Node2_2;
    Node2_1->right = Node2_3;
    Node2_2->right = Node2_4;
    Node2_3->right = Node2_5;

    Solution S1;
    TreeNode *root = S1.mergeTrees(Node1_1, Node2_1);
    // 層次遍歷
    std::queue<TreeNode*> q;
    q.push(root);
    while(!q.empty()){
        TreeNode *tmp = q.front();
        q.pop();
        std::cout << tmp->val << " ";
        if(tmp->left != nullptr) q.push(tmp->left);
        if(tmp->right != nullptr) q.push(tmp->right);
    }
    std::cout << std::endl;
    return 0;
}

17--二叉搜索樹中的搜索

代碼隨想錄筆記--二叉樹篇,數(shù)據(jù)結構&LeetCode,數(shù)據(jù)結構

主要思路：

? ? ? ? 根據(jù)節(jié)點大小，遞歸從左子樹或者右子樹尋找；

#include <iostream>

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* searchBST(TreeNode* root, int val) {
        return dfs(root, val);
    }
    TreeNode* dfs(TreeNode* root, int val){
        if(root == nullptr || root->val == val) return root;

        if(root->val > val){
            return dfs(root->left, val);
        }
        else return dfs(root->right, val);
    }
};

int main(int argc, char* argv[]){
    // root = [4,2,7,1,3], val = 2
    TreeNode *Node1 = new TreeNode(4);
    TreeNode *Node2 = new TreeNode(2);
    TreeNode *Node3 = new TreeNode(7);
    TreeNode *Node4 = new TreeNode(1);
    TreeNode *Node5 = new TreeNode(3);
    Node1->left = Node2;
    Node1->right = Node3;
    Node2->left = Node4;
    Node2->right = Node5;

    int val = 2;
    Solution S1;

    TreeNode *res = S1.searchBST(Node1, val);
    if(res == nullptr) std::cout << "" << std::endl;
    else std::cout << res->val << std::endl;
    return 0;
}

18--驗證二叉搜索樹

代碼隨想錄筆記--二叉樹篇,數(shù)據(jù)結構&LeetCode,數(shù)據(jù)結構

主要思路：

? ? ? ? 遞歸判斷，確保自下而上左子樹節(jié)點都小于根節(jié)點，右子樹節(jié)點都大于根節(jié)點；

#include <iostream>
#include <limits.h>

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:
    bool isValidBST(TreeNode* root) {
        long long max_value = LONG_MAX, min_value = LONG_MIN;
        return dfs(root, max_value, min_value);
    }

    bool dfs(TreeNode *root, long long max_value, long long min_value){
        if(root == nullptr) return true;
        if(root->val >= max_value || root->val <= min_value) return false;
        bool left = dfs(root->left, root->val, min_value);
        bool right = dfs(root->right, max_value, root->val);
        return left && right;
    }
};

int main(int argc, char* argv[]){
    // root = [2, 1, 3]
    TreeNode *Node1 = new TreeNode(2);
    TreeNode *Node2 = new TreeNode(1);
    TreeNode *Node3 = new TreeNode(3);
    Node1->left = Node2;
    Node1->right = Node3;
    Solution S1;

    bool res = S1.isValidBST(Node1);
    if(res) std::cout << "true" << std::endl;
    else std::cout << "false" << std::endl;
    return 0;
}

19--二叉搜索樹的最小絕對差

代碼隨想錄筆記--二叉樹篇,數(shù)據(jù)結構&LeetCode,數(shù)據(jù)結構

主要思路1：

? ? ? ? 利用中序遍歷將二叉搜索樹的元素存放在一個遞增的數(shù)組中，然后遍歷遞增數(shù)組，計算相鄰兩節(jié)點的差值即可；

#include <iostream>
#include <limits.h>
#include <vector>

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:
    int getMinimumDifference(TreeNode* root) {
        std::vector<int> res;
        int min = INT_MAX;
        dfs(root, res);
        for(int i = 1; i < res.size(); i++){
            if(res[i] - res[i-1] < min){
                min = res[i] - res[i-1];
            }
        }
        return min;
    }

    void dfs(TreeNode *root, std::vector<int> &res){
        if(root == nullptr) return;
        dfs(root->left, res);
        res.push_back(root->val);
        dfs(root->right, res);
    }
};

int main(int argc, char* argv[]){
    // root = [4,2,6,1,3]
    TreeNode *Node1 = new TreeNode(4);
    TreeNode *Node2 = new TreeNode(2);
    TreeNode *Node3 = new TreeNode(6);
    TreeNode *Node4 = new TreeNode(1);
    TreeNode *Node5 = new TreeNode(3);

    Node1->left = Node2;
    Node1->right = Node3;
    Node2->left = Node4;
    Node2->right = Node5;

    Solution S1;
    int res = S1.getMinimumDifference(Node1);
    std::cout << res << std::endl;
    return 0;
}

主要思路2：

? ? ? ? 利用雙指針遞歸，記錄中序遍歷的前一個節(jié)點和當前節(jié)點，計算兩個節(jié)點的差值，并更新最小值即可；

#include <iostream>
#include <limits.h>

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:
    int getMinimumDifference(TreeNode* root) {
        dfs(root);
        return min;
    }

    void dfs(TreeNode *cur){
        if(cur == nullptr) return;
        dfs(cur->left);
        if(pre != nullptr){
            min = std::min(min, cur->val - pre->val);
        }
        pre = cur;
        dfs(cur->right);
    }

private:
    int min = INT_MAX;
    TreeNode *pre = nullptr;
};

int main(int argc, char* argv[]){
    // root = [4,2,6,1,3]
    TreeNode *Node1 = new TreeNode(4);
    TreeNode *Node2 = new TreeNode(2);
    TreeNode *Node3 = new TreeNode(6);
    TreeNode *Node4 = new TreeNode(1);
    TreeNode *Node5 = new TreeNode(3);

    Node1->left = Node2;
    Node1->right = Node3;
    Node2->left = Node4;
    Node2->right = Node5;

    Solution S1;
    int res = S1.getMinimumDifference(Node1);
    std::cout << res << std::endl;
    return 0;
}

20--二叉搜索樹中的眾數(shù)

代碼隨想錄筆記--二叉樹篇,數(shù)據(jù)結構&LeetCode,數(shù)據(jù)結構

主要思路：

? ? ? ? 基于雙指針中序遍歷二叉搜索樹，判斷pre指針和cur指針指向的節(jié)點是否相同，如果相同，則當前節(jié)點的 count++，否則 count = 1；

? ? ? ? 當某個節(jié)點的出現(xiàn)頻率與max_count相同時，將其放入結果數(shù)組；

????????更新眾數(shù)時需要清空結果數(shù)組，并放入最大眾數(shù)對應的節(jié)點；

#include <iostream>
#include <vector>

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:
    std::vector<int> findMode(TreeNode* root) {
        dfs(root);
        return res;
    }

    void dfs(TreeNode* cur){
        if(cur == nullptr) return;
        // 左
        dfs(cur->left);
        if(pre == nullptr || cur->val != pre->val){
            count = 1;
        }
        else{
            count++;
        }

        if(count == max_count) res.push_back(cur->val);
        if(count > max_count){
            max_count = count;
            res.clear();
            res.push_back(cur->val);
        }

        pre = cur; // 雙指針
        dfs(cur->right);
    }

private:
    int max_count = 0;
    int count = 0;
    std::vector<int> res;
    TreeNode *pre = nullptr;
};

int main(int argc, char* argv[]){
    // root = [1,null,2,2]
    TreeNode *Node1 = new TreeNode(1);
    TreeNode *Node2 = new TreeNode(2);
    TreeNode *Node3 = new TreeNode(2);

    Node1->right = Node2;
    Node2->left = Node3;

    Solution S1;
    std::vector<int> res = S1.findMode(Node1);
    for(int v : res) std::cout << v << " ";
    std::cout << std::endl;
    return 0;
}

21--二叉樹的最近公共祖先

代碼隨想錄筆記--二叉樹篇,數(shù)據(jù)結構&LeetCode,數(shù)據(jù)結構

主要思路：

? ? ? ? 遞歸自底向上尋找，找到目標節(jié)點就返回；對于一個節(jié)點，若其左右子樹均找到目標節(jié)點，則該節(jié)點即為最近公共祖先；

? ? ? ? 若只有一顆子樹能找到目標節(jié)點，則該子樹的返回結果就是最近公共祖先；

#include <iostream>
#include <string>
#include <vector>

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

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        TreeNode* res = dfs(root, p, q);
        return res;
    }

    TreeNode* dfs(TreeNode* root, TreeNode* p, TreeNode* q){
        if(root == nullptr) return nullptr;
        if(root->val == p->val || root->val == q->val) return root;
        TreeNode* left = dfs(root->left, p, q);
        TreeNode* right = dfs(root->right, p, q);
        if(left != nullptr && right != nullptr) return root;
        else if(left != nullptr && right == nullptr) return left;
        else return right;
    }
};

int main(int argc, char* argv[]){
    // root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
    TreeNode* Node1 = new TreeNode(3);
    TreeNode* Node2 = new TreeNode(5);
    TreeNode* Node3 = new TreeNode(1);
    TreeNode* Node4 = new TreeNode(6);
    TreeNode* Node5 = new TreeNode(2);
    TreeNode* Node6 = new TreeNode(0);
    TreeNode* Node7 = new TreeNode(8);
    TreeNode* Node8 = new TreeNode(7);
    TreeNode* Node9 = new TreeNode(4);

    Node1->left = Node2;
    Node1->right = Node3;
    Node2->left = Node4;
    Node2->right = Node5;
    Node3->left = Node6;
    Node3->right  = Node7;
    Node5->left = Node8;
    Node5->right = Node9;

    Solution S1;
    TreeNode *res = S1.lowestCommonAncestor(Node1, Node2, Node3);
    if(res != nullptr) std::cout << res->val << std::endl;
    else std::cout << "null" << std::endl;
    return 0;
}

22--二叉搜索樹的最近公共祖先

代碼隨想錄筆記--二叉樹篇,數(shù)據(jù)結構&LeetCode,數(shù)據(jù)結構

主要思路：

? ? ? ? 遞歸尋找，根據(jù)節(jié)點大小判斷在左子樹還是右子樹尋找目標節(jié)點；

? ? ? ? 對于一個節(jié)點，假如其值在兩個目標節(jié)點中間，則該節(jié)點為最近公共祖先；

#include <iostream>
#include <string>
#include <vector>

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

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        TreeNode* res = dfs(root, p, q);
        return res;
    }
    TreeNode* dfs(TreeNode* root, TreeNode* p, TreeNode* q){
        if(root == nullptr) return nullptr;
        if(root->val > p->val && root->val > q->val){
            return dfs(root->left, p, q);
        }
        else if(root->val < p->val && root->val < q->val){
            return dfs(root->right, p, q);
        }
        else return root;
    }
};

int main(int argc, char* argv[]){
    // root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
    TreeNode* Node1 = new TreeNode(6);
    TreeNode* Node2 = new TreeNode(2);
    TreeNode* Node3 = new TreeNode(8);
    TreeNode* Node4 = new TreeNode(0);
    TreeNode* Node5 = new TreeNode(4);
    TreeNode* Node6 = new TreeNode(7);
    TreeNode* Node7 = new TreeNode(9);
    TreeNode* Node8 = new TreeNode(3);
    TreeNode* Node9 = new TreeNode(5);

    Node1->left = Node2;
    Node1->right = Node3;
    Node2->left = Node4;
    Node2->right = Node5;
    Node3->left = Node6;
    Node3->right  = Node7;
    Node5->left = Node8;
    Node5->right = Node9;

    Solution S1;
    TreeNode *res = S1.lowestCommonAncestor(Node1, Node2, Node3);
    if(res != nullptr) std::cout << res->val << std::endl;
    else std::cout << "null" << std::endl;
    return 0;
}

23--二叉搜索樹中的插入操作

代碼隨想錄筆記--二叉樹篇,數(shù)據(jù)結構&LeetCode,數(shù)據(jù)結構

主要思路：

? ? ? ? 任意一個節(jié)點的插入位置都能在葉子節(jié)點上找到，因此只需要遞歸遍歷找到合適的葉子節(jié)點位置，將插入節(jié)點放到葉子節(jié)點位置即可；

#include <iostream>
#include <vector>
#include <queue>

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* insertIntoBST(TreeNode* root, int val) {
        return dfs(root, val);
    }

    TreeNode* dfs(TreeNode* root, int val){
        if(root == nullptr){ // 找到葉子節(jié)點位置了
            TreeNode* target = new TreeNode(val);
            return target;
        }

        if(root->val > val){
            root->left = dfs(root->left, val);
        }
        else if(root->val < val){
            root->right = dfs(root->right, val);
        }

        return root;
    }
};


int main(int argc, char* argv[]){
    TreeNode* Node1 = new TreeNode(4);
    TreeNode* Node2 = new TreeNode(2);
    TreeNode* Node3 = new TreeNode(7);
    TreeNode* Node4 = new TreeNode(1);
    TreeNode* Node5 = new TreeNode(3);

    Node1->left = Node2;
    Node1->right = Node3;
    Node2->left = Node4;
    Node2->right = Node5;

    int val = 5;
    Solution S1;
    TreeNode *res = S1.insertIntoBST(Node1, val);

    // 層次遍歷
    std::queue<TreeNode *> q;
    q.push(res);
    while(!q.empty()){
        TreeNode* tmp = q.front();
        q.pop();
        std::cout << tmp->val << " ";
        if(tmp->left != nullptr){
            q.push(tmp->left);
        }
        if(tmp->right != nullptr){
            q.push(tmp->right);
        }
    }
    std::cout << std::endl;

    return 0;
}

24--刪除二叉搜索樹中的節(jié)點

代碼隨想錄筆記--二叉樹篇,數(shù)據(jù)結構&LeetCode,數(shù)據(jù)結構

主要思路：

? ? ? ? 刪除節(jié)點有以下 5 種情況：

① 找不到刪除的節(jié)點，返回 nullptr；

② 刪除節(jié)點的左右孩子均為空（即為葉子節(jié)點），返回 nullptr；

③ 刪除節(jié)點的左不空，右空，返回左孩子；

④ 刪除節(jié)點的右不空，左空，返回右孩子；

⑤ 刪除節(jié)點的左右均不空，記錄刪除節(jié)點的左孩子，然后遞歸刪除節(jié)點的右孩子，找到最左邊的葉子節(jié)點，將原先記錄的刪除節(jié)點的左孩子放到葉子結點的左孩子中；

#include <iostream>
#include <vector>
#include <queue>

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* deleteNode(TreeNode* root, int key) {
        return dfs(root, key);
    }

    TreeNode* dfs(TreeNode* root, int key){
        if(root == nullptr) return nullptr; // 刪除節(jié)點不存在
        if(root->val == key){ // 找到刪除的葉子節(jié)點
            if(root->left == nullptr && root->right == nullptr){
                TreeNode *tmp = root;
                delete(tmp);
                return nullptr;
            }
            else if(root->left != nullptr && root->right == nullptr){
                TreeNode *tmp = root;
                TreeNode *left = root->left;
                delete(tmp);
                return left;
            }
            else if(root->left == nullptr && root->right != nullptr){
                TreeNode *tmp = root;
                TreeNode *right = root->right;
                delete(tmp);
                return right;
            }
            else{ // root->left != nullptr && root->right != nullptr
                TreeNode* left = root->left; // 記錄其左子樹
                TreeNode* right = root->right;
                TreeNode* cur = root->right;
                while(cur -> left != nullptr){ // 遞歸其右子樹
                    cur = cur->left;
                }
                cur->left = left; // 將左子樹作為右子樹最左邊的葉子節(jié)點的左孩子
                delete(root);
                return right; // 返回右子樹
            }
        }
        if(root->val > key) root->left = dfs(root->left, key);
        else root->right = dfs(root->right, key);
        return root;
    }  
};

int main(int argc, char* argv[]){
    TreeNode* Node1 = new TreeNode(5);
    TreeNode* Node2 = new TreeNode(3);
    TreeNode* Node3 = new TreeNode(6);
    TreeNode* Node4 = new TreeNode(2);
    TreeNode* Node5 = new TreeNode(4);
    TreeNode* Node6 = new TreeNode(7);

    Node1->left = Node2;
    Node1->right = Node3;
    Node2->left = Node4;
    Node2->right = Node5;
    Node3->right = Node6;

    int key = 3;
    Solution S1;
    TreeNode *res = S1.deleteNode(Node1, key);

    // 層次遍歷
    std::queue<TreeNode *> q;
    q.push(res);
    while(!q.empty()){
        TreeNode* tmp = q.front();
        q.pop();
        std::cout << tmp->val << " ";
        if(tmp->left != nullptr){
            q.push(tmp->left);
        }
        if(tmp->right != nullptr){
            q.push(tmp->right);
        }
    }
    std::cout << std::endl;

    return 0;
}

25--修建二叉搜索樹

代碼隨想錄筆記--二叉樹篇,數(shù)據(jù)結構&LeetCode,數(shù)據(jù)結構

主要思路：

? ? ? ? 對于小于左邊界的節(jié)點，則其左子樹所有節(jié)點都會小于左邊界，因此可以舍棄；但仍需要遞歸判斷其右子樹；

? ? ? ? 對于大于右邊界的節(jié)點，則其右子樹所有節(jié)點都會大于右邊界，因此可以舍棄；但仍需要遞歸判斷其左子樹；

#include <iostream>
#include <vector>
#include <queue>

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* trimBST(TreeNode* root, int low, int high) {
        return dfs(root, low, high);
    }
    TreeNode* dfs(TreeNode* root, int low, int high){
        if(root == nullptr) return nullptr;
        if(root->val < low){
            return dfs(root->right, low, high);
        }
        if(root->val > high){
            return dfs(root->left, low, high);
        }

        root->left = dfs(root->left, low, high);
        root->right = dfs(root->right, low, high);
        return root;
    }
};

int main(int argc, char* argv[]){
    // root = [1,0,2], low = 1, high = 2
    TreeNode* Node1 = new TreeNode(1);
    TreeNode* Node2 = new TreeNode(0);
    TreeNode* Node3 = new TreeNode(2);

    Node1->left = Node2;
    Node1->right = Node3;

    int low = 1, high = 2;
    Solution S1;
    TreeNode *res = S1.trimBST(Node1, low, high);

    // 層次遍歷
    std::queue<TreeNode *> q;
    q.push(res);
    while(!q.empty()){
        TreeNode* tmp = q.front();
        q.pop();
        std::cout << tmp->val << " ";
        if(tmp->left != nullptr){
            q.push(tmp->left);
        }
        if(tmp->right != nullptr){
            q.push(tmp->right);
        }
    }
    std::cout << std::endl;

    return 0;
}

26--將有序數(shù)組轉換為二叉搜索樹

代碼隨想錄筆記--二叉樹篇,數(shù)據(jù)結構&LeetCode,數(shù)據(jù)結構

主要思路：

? ? ? ? 二分有序數(shù)組，遞歸構造左子樹和右子樹；

#include <iostream>
#include <queue>
#include <vector>

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* sortedArrayToBST(std::vector<int>& nums) {
        TreeNode* res = dfs(nums, 0, nums.size() - 1);
        return res;
    }

    TreeNode* dfs(std::vector<int>& nums, int left, int right){
        if(left > right) {
            return nullptr;
        }
        int mid = left + (right - left) / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = dfs(nums, left, mid - 1);
        root->right = dfs(nums, mid + 1, right);
        return root;
    }
};

int main(int argc, char* argv[]){
    // nums = [-10,-3,0,5,9]
    std::vector<int> nums = {-10, -3, 0, 5, 9};
    Solution S1;
    TreeNode *res = S1.sortedArrayToBST(nums);
    // 層次遍歷二叉樹
    std::queue<TreeNode*> q;
    q.push(res);
    while(!q.empty()){
        TreeNode* tmp = q.front();
        q.pop();
        std::cout << tmp->val << " ";
        if(tmp->left != nullptr) q.push(tmp->left);
        if(tmp->right != nullptr) q.push(tmp->right);
    }
    return 0;
}

27--把二叉搜索樹轉換為累加樹

代碼隨想錄筆記--二叉樹篇,數(shù)據(jù)結構&LeetCode,數(shù)據(jù)結構

主要思路：

? ? ? ?二叉搜索樹按照左→根→右的順序遍歷是一個升序數(shù)組，則按照右 → 根 → 左的順序遍歷就是一個降序數(shù)組；

? ? ? ? 因此可以按照降序的順序遍歷，將當前節(jié)點的值更新為當前節(jié)點的值+前一個節(jié)點的值；

? ? ? ? 用一個變量 pre 來記錄上一個節(jié)點的值（類似于求二叉樹眾數(shù)的雙指針），每遍歷一個節(jié)點，更新 pre 的值；文章來源地址http://www.zghlxwxcb.cn/news/detail-693367.html

#include <iostream>
#include <queue>
#include <vector>

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* convertBST(TreeNode* root) {
        dfs(root);
        return root;
    }

    void dfs(TreeNode* cur){
        if(cur == nullptr) return;
        // 右
        dfs(cur->right);
        // 中
        cur->val = pre + cur->val;
        pre = cur->val; // 更新pre
        // 左
        dfs(cur->left);
    }
private:
    int pre = 0;
};

int main(int argc, char* argv[]){
    // [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
    TreeNode* Node1 = new TreeNode(4);
    TreeNode* Node2 = new TreeNode(1);
    TreeNode* Node3 = new TreeNode(6);
    TreeNode* Node4 = new TreeNode(0);
    TreeNode* Node5 = new TreeNode(2);
    TreeNode* Node6 = new TreeNode(5);
    TreeNode* Node7 = new TreeNode(7);
    TreeNode* Node8 = new TreeNode(3);
    TreeNode* Node9 = new TreeNode(8);

    Node1->left = Node2;
    Node1->right = Node3;
    Node2->left = Node4;
    Node2->right = Node5;
    Node3->left = Node6;
    Node3->right = Node7;
    Node5->right = Node8;
    Node7->right = Node9;

    Solution S1;
    TreeNode *res = S1.convertBST(Node1);
    // 層次遍歷二叉樹
    std::queue<TreeNode*> q;
    q.push(res);
    while(!q.empty()){
        TreeNode* tmp = q.front();
        q.pop();
        std::cout << tmp->val << " ";
        if(tmp->left != nullptr) q.push(tmp->left);
        if(tmp->right != nullptr) q.push(tmp->right);
    }
    return 0;
}

到了這里，關于代碼隨想錄筆記--二叉樹篇的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！