天天看點
傳回

LeetCode樹專題

LeetCode樹專題，樹的周遊，二叉搜尋樹，二叉樹

LeetCode樹專題

98. 驗證二叉搜尋樹

二叉搜尋樹，每個結點的值都有一個範圍

LeetCode樹專題
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return dfs(root,INT_MIN,INT_MAX);
    }
    bool dfs(TreeNode* root,long long l,long long  r){
        if(!root) return true; 
        //判斷目前結點
        if(root->val < l || root->val > r) return false;
        //遞歸判斷左右子節點
        return dfs(root->left,l,root->val - 1ll) && dfs(root->right,root->val+1ll,r);
    }
};

94. 二叉樹的中序周遊

二叉樹中序周遊的疊代寫法

模拟中序周遊

LeetCode樹專題
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> stk;
        auto p = root;
        while(p || stk.size()){
            while(p){ //1.把左子樹全部加入棧中
                stk.push(p);
                p = p->left;
            }
            p = stk.top(); //2.取棧首 輸出棧首
            stk.pop();
            result.push_back(p->val);
            p = p->right; //3.轉到右子樹
        }
        return result;
    }
};

101. 對稱二叉樹

用遞歸和疊代兩種做法

LeetCode樹專題
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return dfs(root->left,root->right);
    }
    bool dfs(TreeNode* p,TreeNode* q){
        if(!p || !q) return !p && !q; //左右不能一空一不空
        //1.比較目前兩結點的值 
		//2.比較p結點左子樹和q結點右子樹
		//3.比較p結點右子樹和q結點左子樹
        return p->val == q->val && 
		dfs(p->left,q->right) && dfs(p->right,q->left); 
    }
};

疊代：左邊左中右，右邊右中左；每次周遊對應兩個結點比較值是否相等

類似LeetCode94的疊代周遊二叉樹的思路

LeetCode樹專題

105. 從前序與中序周遊序列構造二叉樹

假設樹中沒有重複的元素。

根據一棵樹的前序周遊與中序周遊構造二叉樹。

LeetCode樹專題

前序序列确定根

在中序序列中找到根的值，那麼根左邊為左子樹序列，右邊為右子樹序列

前序序列下一個結點是左子樹的根；

前序序列目前位置加上左子樹的大小的下一個原始就是右子樹的根；

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    unordered_map<int,int> mp;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        for(int i=0;i<n;i++) mp[inorder[i]] = i; //哈希表預統計中序各元素所在下标
        return dfs(preorder,inorder,0,n-1,0,n-1);
    }
    TreeNode* dfs(vector<int>& preorder,vector<int>& inorder,int pl,int pr,int il,int ir){
        if(pl > pr) return NULL;
        int value = preorder[pl];
        int pos = mp[value]; //找到根在中序序列中的位置
        int len = pos-il; //左子樹元素個數
        auto root = new TreeNode(value); //建立根
        root->left = dfs(preorder,inorder,pl+1,pl+len,il,pos-1); //建左子樹
        root->right = dfs(preorder,inorder,pl+len+1,pr,pos+1,ir); //建右子樹
        return root;
    }
};

102. 二叉樹的層序周遊

以層為機關

bfs分别統計每一層

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if(!root) return result; //邊界判斷 特判root為空
        queue<TreeNode*> q;
        q.push(root);
        while(q.size()){
            vector<int> levelList;
            int len = q.size(); //循環剛進來 代表上一層的元素個數
            for(int i=1;i<=len;i++){ 
            	//把目前層每一個元素分别出隊 并把左右結點入隊
                auto top = q.front();
                q.pop();
                levelList.push_back(top->val);
                if(top->left) q.push(top->left);
                if(top->right) q.push(top->right);
            }
            result.push_back(levelList);
        }
        return result;
    }
};

236. 二叉樹的最近公共祖先

思路：來源leetcode題解

LeetCode樹專題
/**
 * Definition for a binary tree node.
 * 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) {
        //遞歸出口
        if(root == NULL || root == p || root == q) return root;

        //遞歸統計左右結點
        auto left = lowestCommonAncestor(root->left,p,q);
        auto right = lowestCommonAncestor(root->right,p,q);

        //隻在一個子樹上
        if(left == NULL) return right;
        if(right == NULL) return left;

        //否則left和right都非空
        //說明一個結點在其左子樹 另一個結點在右子樹那麼目前結點就是最近公共祖先
        return root; 
    }
};

543. 二叉樹的直徑

直徑：樹中最長的路徑(從一點到另一點)

LeetCode樹專題
LeetCode樹專題

注意：因為一開始不确定最高點是哪個，根節點不一定是最高點，比如下圖樣例

是以在dfs的過程上枚舉最高點，就是計算目前結點下ans的最大值

LeetCode樹專題
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int ans = 0; //最優值
    int diameterOfBinaryTree(TreeNode* root) {
        dfs(root);
        return ans;
    }
    int dfs(TreeNode* root){
        if(!root) return 0;
        int left = dfs(root->left);
        int right = dfs(root->right);
        //加入目前結點後的最優值: 左子樹深度 + 右子樹深度
        ans = max(ans,left+right); //更新目前節點下 最長直徑長度
        return max(left,right); //傳回目前樹上 左右子樹的最大值
    }
};

其它做法：

先找到一個深度最深的端點(最高點)，再把最高點作為根dfs找到新的最深距離

https://www.cnblogs.com/fisherss/p/10914820.html

124. 二叉樹中的最大路徑和

從樹中任意節點出發，達到任意節點的序列的最大路徑和

和LeetCode543思路一樣，dfs的過程中枚舉最優點(最高點)，即最優點下路徑和最大，其對應所在的一條路徑上權值和最大，所在的路徑為左子樹路徑+本身+右子樹

LeetCode樹專題
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int ans = INT_MIN;
    int maxPathSum(TreeNode* root) {
        dfs(root);
        return ans;
    }

    //從目前結點root向下走的最大值
    int dfs(TreeNode* root){
        if(!root) return 0;
        int left = dfs(root->left);
        int right = dfs(root->right);
        //dfs枚舉到最優點下 更新加入目前結點後的最優值  
        
        ans = max(ans,left+root->val+right); //左邊最大值 + 自己 + 右邊最大值

        /*
        //下面三行都可以省略替代為上一行 
        //因為dfs左右子樹後 左右子樹已達最優 隻要再加入目前結點的值就行
        ans = max(ans,root->val);
        ans = max(ans,left+root->val);
        ans = max(ans,right+root->val);
        */
        //三種情況和0比較
        return max(0,max(root->val,max(left+root->val,right+root->val)));
    }
};

173. 二叉搜尋樹疊代器

題目描述：

實作一個二叉搜尋樹疊代器。你将使用二叉搜尋樹的根節點初始化疊代器。

調用

next()

将傳回二叉搜尋樹中的下一個最小的數。

題目要求：

LeetCode樹專題

思路：

二叉搜尋樹每次傳回一個最小的數，就相當于對二叉搜尋樹進行中序周遊

因為二叉搜尋樹的左子樹都比根小，右子樹都比根大；即左、中、右的值依次增大

遞歸方式(不滿足空間要求)：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class BSTIterator {
public:
    vector<int> v;
    int pos = 0;
    BSTIterator(TreeNode* root) {
        dfs(root);
    }

    void dfs(TreeNode* root){
        if(!root) return;
        dfs(root->left);
        v.push_back(root->val);
        dfs(root->right);
    }
    
    /** @return the next smallest number */
    int next() {
        return v[pos++];
    }
    
    /** @return whether we have a next smallest number */
    bool hasNext() {
        if(pos < v.size()) return true;
        return false;
    }
};

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator* obj = new BSTIterator(root);
 * int param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */

疊代方式(用棧來模拟中序周遊)：

參考LeetCode94，隻不過是把疊代拆開寫了

滿足next函數記憶體是O(h)，即棧中最多加入了一列深度下的節點

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class BSTIterator {
public:
    stack<TreeNode*> stk;
    BSTIterator(TreeNode* root) {
        while(root){ //初始加入左子樹入棧
            stk.push(root);
            root = root->left;
        }
    }
    
    /** @return the next smallest number */
    int next() { //O(h)
        auto p = stk.top(); //二叉搜尋樹中序的棧頂一定是最小的
        stk.pop();
        int result = p->val;
        p = p->right; //左子樹周遊完了 根也周遊完了 就移向右子樹
        while(p){
            stk.push(p);
            p = p->left;
        }
        return result;
    }
    
    /** @return whether we have a next smallest number */
    bool hasNext() {
        return !stk.empty();
    }
};

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator* obj = new BSTIterator(root);
 * int param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */

297. 二叉樹的序列化與反序列化

序列化相當于先序周遊序列，NULL值用#代替；

反序列化相當于用帶#表示空值的先序序列來建樹(本來隻用先序序列無法建樹，但是這裡使用了#來代表葉節點孩子的值為空，就可以用先序建樹了)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string data;
        dfs1(root,data);
        return data;
    }

    void dfs1(TreeNode* root,string &data){
        if(!root){
            data += "#,";
            return;
        }
        data += to_string(root->val) + ','; //先序周遊
        dfs1(root->left,data);
        dfs1(root->right,data);
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        int index = 0;
        return dfs2(data,index);
    }

    TreeNode* dfs2(string &data,int &index){
        if(data[index] == '#'){ //遇到#号 要消耗一個,和一個#
            index+=2; 
            return NULL;
        }
        bool is_minus = false;
        if(data[index] == '-') { //判斷是否是負數
            is_minus = true;
            index++;
        }
        int value = 0;
        while(data[index] != ','){ //求這個數的值 到下一個逗号結束
            value = value * 10 + (data[index] - '0');
            index++;
        }
        index++;
        if(is_minus) value = -value; //負數
        auto root = new TreeNode(value); //建立根節點
        root->left = dfs2(data,index); //遞歸求左右子樹
        root->right = dfs2(data,index);
        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));
二叉搜尋樹leetcodedfsbfs樹
上一篇: Event Loop、 宏任務和微任務
下一篇: PHP+vue Web端使用支付寶支付