二叉樹系列匯總，持續更新！

相關文章匯總：

• 動態規劃系列匯總，持續更新！
• 最小路徑和問題匯總，持續更新！
• 跳躍游戲系列匯總，持續更新！

一、構造二叉樹

// Definition for a binary tree node.
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:

    //將二叉搜索樹轉換為一個排序好的vector
    void orderTree2vector(TreeNode *node, vector<int> &vec)
    {
        if(node==nullptr) return;

        orderTree2vector(node->left, vec);
        vec.push_back(node->val);
        orderTree2vector(node->right, vec);
    }

    //將二叉搜索樹轉換成遞增順序搜索樹
    TreeNode* increasingBST(TreeNode* root) {
        vector <int>vec;
        orderTree2vector(root, vec);
        //創建一個新的節點
        TreeNode *newNode = new TreeNode(-1);
        TreeNode *currNode = newNode;

        for(int value: vec)
        {
            currNode->right = new TreeNode(value);
            currNode = currNode->right;
        }
        return newNode->right;
    }
};

復雜度分析：

• 時間復雜度：O(n)，其中 n 是二叉搜索樹的節點總數，
• 空間復雜度：O(n)，其中 n 是二叉搜索樹的節點總數，需要長度為 n 的串列保存二叉搜索樹的所有節點的值，

提交結果：

三、二叉搜索樹范圍和（LeetCode 938）

題目

給定二叉搜索樹的根結點 root，回傳值位于范圍 [low, high] 之間的所有結點的值的和，

提示：
樹中節點數目在范圍 [1, 2 * 104] 內
1 <= Node.val <= 105
1 <= low <= high <= 105
所有 Node.val 互不相同

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/range-sum-of-bst
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，

題解

本題可以通過中序遍歷將二叉樹中的值按順序存盤到一個陣列中，然后再計算[low, high]之間的數的和，但是并不推薦這么做，我們可以利用二叉搜索樹本身的結構，以及有序性的性質 ，利用更小的復雜度來解決本題，

解法：深度優先搜索

按深度優先搜索的順序計算范圍和，記當前子樹根節點為 root，分以下四種情況討論：

• root 節點為空，說明已經搜索到葉子節點（沒有子節點），回傳0，
• root 節點的值 root->value > high，則無需考慮右子樹，回傳左子樹的范圍和，
• root 節點的值 root->value < low，則無需考慮左子樹，回傳右子樹的范圍和，
• root 節點的值 low< root->value < high 此時應回傳 root 節點的值、左子樹的范圍和、右子樹的范圍和這三者之和，

C++實作如下：

class Solution {
public:
    int rangeSumBST(TreeNode *root, int low, int high) {
        if (root == nullptr) {
            return 0;
        }
        if (root->val > high) {
            return rangeSumBST(root->left, low, high);
        }
        if (root->val < low) {
            return rangeSumBST(root->right, low, high);
        }
        return root->val + rangeSumBST(root->left, low, high) + rangeSumBST(root->right, low, high);
    }
};

復雜度分析：

• 時間復雜度：O(n)，其中 nn 是二叉搜索樹的節點數，
• 空間復雜度：O(n)，空間復雜度主要取決于堆疊空間的開銷，

四、二叉搜索樹的第k大節點

題目

給定一棵二叉搜索樹，請找出其中第k大的節點，

限制：
1 ≤ k ≤ 二叉搜索樹元素個數

原題：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/

題解

class Solution {
public:
	// 倒序遍歷二插入，將數字從大到小存入陣列vec中
    void orderTree2vector(TreeNode* root, vector<int> &vec)
    {
        if(root==nullptr) return;
        orderTree2vector(root->right, vec);
        vec.push_back(root->val);
        orderTree2vector(root->left, vec);
    }
	// 取vec的第k大數即可
    int kthLargest(TreeNode* root, int k) {
        vector<int> vec;
        orderTree2vector(root, vec);
        return vec[k-1];
    }
};