{"id":1177,"date":"2024-10-28T11:48:02","date_gmt":"2024-10-28T03:48:02","guid":{"rendered":"http:\/\/114.55.108.251\/?p=1177"},"modified":"2025-01-14T11:22:24","modified_gmt":"2025-01-14T03:22:24","slug":"%e5%8a%9b%e6%89%a3%e5%88%b7%e9%a2%98%e4%b9%8b%e4%ba%8c%e5%8f%89%e6%a0%91","status":"publish","type":"post","link":"https:\/\/guapicoding.com\/?p=1177","title":{"rendered":"\u529b\u6263\u9898\u8bb0\u4e4b\u4e8c\u53c9\u6811"},"content":{"rendered":"\n

More content\uff1a<\/strong><\/em>LeetCode hot100@\u4e8c\u53c9\u6811<\/strong><\/a><\/p>\n\n\n\n

257. \u4e8c\u53c9\u6811\u7684\u6240\u6709\u8def\u5f84<\/a>\u274c<\/h2>\n\n\n\n

\u9012\u5f52\u56de\u6eaf<\/em><\/strong><\/p>\n\n\n\n

\u9012\u5f52\u4e09\u6b65\u8d70\uff0c\u4f46\u8981\u6ce8\u610f\u5728\u4e8c\u53c9\u6811\u7684\u9012\u5f52\u4e2d\u5355\u5c42\u903b\u8f91\u4e00\u822c\u8981\u5305\u62ec\u4e2d\u5de6\u53f3\u4e09\u90e8\u5206<\/em><\/strong>\uff08\u987a\u5e8f\u4f9d\u524d\u4e2d\u540e\u904d\u5386\u800c\u5b9a\uff09<\/strong><\/em><\/p>\n\n\n\n

class Solution {\npublic:\n    void traversal(TreeNode *cur, vector<string> &res, vector<int> &path) {\n        \/\/\u56e0\u4e3a\u8c03\u7528\u9012\u5f52\u65f6\u6ca1\u6709\u5904\u7406root \u6240\u4ee5\u8981\u5148\u5904\u7406\u4e00\u4e0b\u5f53\u4e0b\u8282\u70b9 \u540e\u4e24\u9898\u5219\u4e0d\u540c\n        path.push_back(cur->val); \/\/\u5355\u5c42\u903b\u8f91\u90e8\u5206 \u4e2d\n\n        \/\/\u7ec8\u6b62\u6761\u4ef6\u4e0d\u4f1a\u662f\u7a7a\u8282\u70b9 \u56e0\u4e3a\u7a7a\u8282\u70b9\u6839\u672c\u65e0\u6cd5\u8fdb\u5165\u9012\u5f52\n        if(!cur->left && !cur->right) { \/\/\u9047\u5230\u53f6\u5b50\u8282\u70b9 \u610f\u5473\u7740\u4e00\u6761\u8def\u5f84\n            string s;\n            for(int i = 0; i < path.size() - 1; i++) {\n                s += to_string(path[i]); \/\/\u5c06\u6574\u578b\u8f6c\u6362\u4e3a\u5b57\u7b26\u4e32\n                s += \"->\";\n            }\n            s += to_string(path[path.size()-1]);\n            res.push_back(s);\n            return ;\n        } \n\n        if(cur->left) { \/\/\u5355\u5c42\u903b\u8f91\u90e8\u5206 \u5de6\n            traversal(cur->left, res, path);\n            path.pop_back(); \/\/\u56de\u6eaf\uff01\n        }\n        if(cur->right) { \/\/\u5355\u5c42\u903b\u8f91\u90e8\u5206 \u53f3\n            traversal(cur->right, res, path);\n            path.pop_back(); \/\/\u56de\u6eaf\uff01\n        }\n    }\n    vector<string> binaryTreePaths(TreeNode* root) {\n        vector<string> res;\n        vector<int> path; \/\/\u8bb0\u5f55\u8def\u5f84\u8282\u70b9val\n        \n        traversal(root, res, path);\n\n        return res;\n    }\n};<\/code><\/pre>\n\n\n\n
\n\n\n\n
112. \u8def\u5f84\u603b\u548c<\/a>\u274c<\/h2>\n\n\n\n
\u9012\u5f52\u56de\u6eaf \u60f3\u6e05\u695a\u8fd4\u56defalse\u56de\u6eaf\u7684\u8fc7\u7a0b<\/em><\/strong><\/p>\n\n\n\n
class Solution {\npublic:\n    bool travseral(TreeNode* cur, int sum) {\n        \/\/\u7ec8\u6b62\u6761\u4ef6\n        if(!cur->left && !cur->right && !sum) return true;\n        if(!cur->left && !cur->right) return false;\n        \n        if(cur->left) {\n            sum -= cur->left->val;\n            \/\/\u7528\u4e8e\u7ec8\u6b62\u6761\u4ef6\u7b2c\u4e8c\u884c\u7684\u5224\u65ad \u5982\u679c\u8fd4\u56defalse \u5c31\u76f4\u63a5\u56de\u6eaf\n            if(travseral(cur->left, sum)) return true;\n            sum += cur->left->val; \/\/\u56de\u6eaf\n        }\n        if(cur->right) {\n            sum -= cur->right->val;\n            if(travseral(cur->right, sum)) return true;\n            sum += cur->right->val; \/\/\u56de\u6eaf\n        }\n\n        return false;\n    }\n    bool hasPathSum(TreeNode* root, int targetSum) {\n        if(!root) return false;\n        \/\/\u7528\u51cf\u53d6\u4ee3\u52a0 \u53ef\u4ee5\u5c11\u4f20\u9012\u4e00\u4e2a\u53c2\u6570\n        return travseral(root, targetSum - root->val); \n\n    }\n};<\/code><\/pre>\n\n\n\n
\n\n\n\n
113. \u8def\u5f84\u603b\u548c II<\/a>\u2705<\/h2>\n\n\n\n
257.\u4e8c\u53c9\u6811\u7684\u6240\u6709\u8def\u5f84 + 112. \u8def\u5f84\u603b\u548c<\/strong><\/em><\/p>\n\n\n\n
class Solution {\npublic:\n    void travseral(TreeNode *cur, vector<vector<int>> &res, vector<int> &path, int sum) {\n        if(!cur->left && !cur->right && !sum) res.push_back(path);\n        if(!cur->left && !cur->right) return ;\n\n        if(cur->left) {\n            sum -= cur->left->val;\n            path.push_back(cur->left->val);\n            travseral(cur->left, res, path, sum);\n            sum += cur->left->val;\n            path.pop_back();\n        }\n        if(cur->right) {\n            sum -= cur->right->val;\n            path.push_back(cur->right->val);\n            travseral(cur->right, res, path, sum);\n            sum += cur->right->val;\n            path.pop_back();\n        }\n\n        return ;\n    }\n    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {\n        vector<vector<int>> res;\n        vector<int> path;\n        if(!root) return res;\n        \/\/\u5148\u628aroot\u6570\u636e\u5904\u7406\u597d\uff08\u5305\u62ecpath\u548c\u4e0b\u9762\u7684sum\uff09\n        \/\/\u8fd9\u6837\u5230\u4e86\u9012\u5f52\u91cc\u5c31\u53ea\u5173\u5fc3\u5de6\u548c\u53f3\u8282\u70b9 \u800c\u4e0d\u7528\u7ba1\u5f53\u4e0b\u8282\u70b9 \u7406\u6e05\u5355\u5c42\u903b\u8f91\n        path.push_back(root->val); \n        travseral(root, res, path, targetSum - root->val);\n\n        return res;\n    }\n};<\/code><\/pre>\n\n\n\n
\n\n\n\n
106. \u4ece\u4e2d\u5e8f\u4e0e\u540e\u5e8f\u904d\u5386\u5e8f\u5217\u6784\u9020\u4e8c\u53c9\u6811<\/a>\u274c<\/h2>\n\n\n\n
\u9012\u5f52\u6784\u9020<\/em><\/strong><\/p>\n\n\n\n
\u6ce8\u610f\u786e\u5b9a\u5de6\u95ed\u53f3\u5f00\u7684\u539f\u5219\u540e \u8981\u8d2f\u5f7b\u6574\u4e2a\u4ee3\u7801<\/em><\/strong><\/p>\n\n\n\n
class Solution {\npublic:\n    TreeNode* traversal(vector<int> &inorder, int inorderBegin, int inorderEnd, vector<int> &postorder, int postorderBegin, int postorderEnd) {\n        if(inorderBegin == inorderEnd) return nullptr;\n\n        int root_val = postorder[postorderEnd - 1];\n        TreeNode *root = new TreeNode(root_val);\n        if(postorderEnd - postorderBegin == 1) return root;\n\n        int cutIndex = 0;\n        \/\/\u4e00\u76f4\u8d2f\u5f7b\u5de6\u95ed\u53f3\u5f00\n        for(cutIndex = inorderBegin; cutIndex < inorderEnd; cutIndex++) {\n            if(inorder[cutIndex] == root_val) break;\n        }\n        \n        \/\/\u5207\u5272\u4e2d\u5e8f\u6570\u7ec4 \u820d\u5f03\u4e2d\u95f4\u90a3\u4e2a\u8282\u70b9\n        int leftInorderBegin = inorderBegin;\n        int leftInorderEnd = cutIndex;\n        int rightInorderBegin = cutIndex + 1;\n        int rightInorderEnd = inorderEnd;\n\n        \/\/\u5207\u5272\u540e\u5e8f\u6570\u7ec4 \u820d\u5f03\u6700\u540e\u90a3\u4e2a\u8282\u70b9\n        int leftPostorderBegin = postorderBegin;\n        int leftPostorderEnd = postorderBegin + leftInorderEnd - leftInorderBegin;\n        int rightPostorderBegin = postorderBegin + leftInorderEnd - leftInorderBegin;\n        int rightPostorderEnd = postorderEnd - 1;\n\n        root->left = traversal(inorder, leftInorderBegin, leftInorderEnd, postorder, leftPostorderBegin, leftPostorderEnd);\n        root->right = traversal(inorder, rightInorderBegin, rightInorderEnd, postorder, rightPostorderBegin, rightPostorderEnd);\n        \n        return root;\n    }\n    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {\n        return traversal(inorder, 0, inorder.size(), postorder, 0, postorder.size());\n    }\n};<\/code><\/pre>\n\n\n\n
\n\n\n\n
700. \u4e8c\u53c9\u641c\u7d22\u6811\u4e2d\u7684\u641c\u7d22<\/a>\u2705<\/h2>\n\n\n\n
\u7b80\u5355<\/em><\/strong><\/p>\n\n\n\n
class Solution {\npublic:\n    TreeNode* searchBST(TreeNode* root, int val) {\n        if(!root) return nullptr;\n\n        if(root->val == val) return root;\n        else if(root->val > val) {\n            return searchBST(root->left, val);\n        } else {\n            return searchBST(root->right, val);\n        }\n\n    }\n};<\/code><\/pre>\n\n\n\n
\n\n\n\n
538. \u628a\u4e8c\u53c9\u641c\u7d22\u6811\u8f6c\u6362\u4e3a\u7d2f\u52a0\u6811<\/a>\u2705<\/h2>\n\n\n\n
\u6a21\u62df\u4e00\u4e0b\u5c31\u6709\u601d\u8def\u4e86 \u53ea\u8981\u662fBST \u4e00\u822c\u90fd\u662f\u4e2d\u5e8f\u904d\u5386 \u4e0d\u7136\u6709\u5e8f\u8fd8\u6709\u4ec0\u4e48\u7528<\/em><\/strong><\/p>\n\n\n\n
class Solution {\nprivate:\n    int sum; \/\/\u6240\u6709\u8282\u70b9\u4e4b\u548c\npublic:\n    void sumTravseral(TreeNode *cur) {  \n        sum += cur->val;\n        if(cur->left) sumTravseral(cur->left);\n        if(cur->right) sumTravseral(cur->right); \n    }\n    void changeTravseral(TreeNode *cur) { \/\/BST \u56e0\u6b64\u4e2d\u5e8f\u904d\u5386 \u7d2f\u52a0\u503c\u9012\u51cf\n        if(cur->left) changeTravseral(cur->left); \/\/\u5de6\n\n        int tmp = cur->val;\n        cur->val = sum; \/\/\u4e2d\n        sum -= tmp;\n\n        if(cur->right) changeTravseral(cur->right); \/\/\u53f3\n    }\n    TreeNode* convertBST(TreeNode* root) {\n        if(!root) return root;\n\n        sumTravseral(root);\n        changeTravseral(root);\n        \n        return root;\n    }\n};<\/code><\/pre>\n\n\n\n
\n\n\n\n
236. \u4e8c\u53c9\u6811\u7684\u6700\u8fd1\u516c\u5171\u7956\u5148<\/a>\u274c<\/h2>\n\n\n\n
\u4ece\u76ee\u6807\u8282\u70b9\u5f00\u59cb\u81ea\u5e95\u5411\u4e0a\u56de\u6eaf\uff08\u53ea\u80fd\u540e\u5e8f\uff09\u4e00\u5c42\u5c42\u4f20\u8fc7\u53bb<\/em><\/strong><\/p>\n\n\n\n
class Solution {\npublic:\n    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {\n        if(!root || root == p || root == q) return root;\n        \/\/\u627e\u67d0\u4e00\u6761\u8def\u5f84\u5c31\u8981\u5728\u9012\u5f52\u4e2d\u53ca\u65f6return\uff0c\u800c\u904d\u5386\u6574\u68f5\u6811\u5c31\u50cf\u4e0b\u9762\u8fd9\u6837\u7528\n        \/\/\u8282\u70b9\u6765\u627f\u63a5\uff0c\u9012\u5f52\u5b8c\u7edf\u4e00\u5904\u7406\u5de6\u53f3\u4e24\u4e2a\u9012\u5f52\uff0c\u5373\u5904\u7406\u540e\u5e8f\u904d\u5386\u7684\u4e2d\u95f4\u8282\u70b9\n        \/\/\u904d\u5386\u6574\u4e2a\u6811\u4e0d\u4ee3\u8868\u8981\u628a\u6bcf\u4e2a\u70b9\u90fd\u5904\u7406 \u6bd4\u5982\u793a\u4f8b\u4e00\u641c\u4e86\u4e09\u4e2a\u70b9\u5c31\u8fd4\u56de\u4e86\n        \/\/\u4f46\u5982\u679cp q\u90fd\u662f\u53f6\u5b50\u8282\u70b9 \u90a3\u5c31\u8981\u641c\u5b8c\u6574\u68f5\u6811\u4e86 \u6bd4\u5982\u4ee3\u7801\u968f\u60f3\u5f55\u7684\u793a\u4f8b\u56fe\n        TreeNode *left = lowestCommonAncestor(root->left, p, q); \/\/\u5de6\n        TreeNode *right = lowestCommonAncestor(root->right, p, q); \/\/\u53f3\n        \/\/\u4e2d:\n        \/\/\u8fd9\u91ccreturn\u7684\u5c31\u662f\u5de6\u53f3\u4e24\u68f5\u5b50\u6811\u5404\u4e00\u4e2ap q \u5f53\u4e0b\u7684root\u5c31\u662f\u6700\u8fd1\u516c\u5171\u7956\u5148\n        if(left && right) return root; \n        \/\/\u8fd9\u91ccreturn\u7684\u5c31\u662f\u5de6\u53f3\u4e24\u68f5\u5b50\u6811\u6700\u591a\u6709\u4e00\u68f5\u641c\u5230\u4e86p\u548cq \u7ee7\u7eed\u5f80\u4e0a\u4f20\u9012\u76f4\u5230\u6839\u8282\u70b9  \n        if(!left && right) return right;\n        else if(left  && !right) return left;\n        else return nullptr;\n    }\n};<\/code><\/pre>\n\n\n\n
\n\n\n\n
235. \u4e8c\u53c9\u641c\u7d22\u6811\u7684\u6700\u8fd1\u516c\u5171\u7956\u5148<\/a>\u2705\u274c<\/h2>\n\n\n\n
\u53ef\u4ee5\u76f4\u63a5copy\u4e0a\u9898236. \u4e8c\u53c9\u6811\u7684\u6700\u8fd1\u516c\u5171\u7956\u5148<\/a>\u4ee3\u7801\u540e\u5e8f\u904d\u5386 \u56e0\u4e3aBST\u4e5f\u662f\u4e8c\u53c9\u6811\u561b \u4f46\u5c31\u6d6a\u8d39\u4e86BST\u7684\u6709\u5e8f\u6027<\/strong><\/em> \u6240\u4ee5\u4e8c\u5206\u7740\u53bb\u641c<\/em><\/strong><\/p>\n\n\n\n
\u5982\u679c\u627e\u5230\u4e00\u4e2a\u8282\u70b9\u503c\u4f4d\u4e8epq\u4e4b\u95f4 \u90a3\u4e48\u8fd9\u4e2a\u8282\u70b9\u4e00\u5b9a\u662fpq\u7684\u516c\u5171\u7956\u5148 \u800c\u4e14\u5c31\u662f\u6700\u8fd1\u7684<\/strong><\/em> \u6240\u4ee5\u4e0d\u9700\u8981\u50cf\u4e0a\u9898\u4e00\u6837\u904d\u5386\u6574\u68f5\u6811 \u627e\u5230\u8282\u70b9\u76f4\u63a5\u8fd4\u56de\u5373\u53ef<\/em><\/strong><\/p>\n\n\n\n
class Solution {\npublic:\n    TreeNode* lowestCommonAncestor(TreeNode* cur, TreeNode* p, TreeNode* q) {\n        if(!cur) return nullptr;\n                                                       \n        if(cur->val > p->val && cur->val > q->val) { \/\/\u5de6\n            TreeNode* left = lowestCommonAncestor(cur->left, p, q);\n            if(left) return left;\n        }\n\n        if(cur->val < p->val && cur->val < q->val) { \/\/\u53f3\n            TreeNode* right = lowestCommonAncestor(cur->right, p, q);\n            if(right) return right;\n        }\n\n        return cur;\n    }\n};<\/code><\/pre>\n\n\n\n
\n\n\n\n
701. \u4e8c\u53c9\u641c\u7d22\u6811\u4e2d\u7684\u63d2\u5165\u64cd\u4f5c<\/a>\u2705<\/h2>\n\n\n\n
\u60f3\u4e00\u4e0b\u641c\u5230\u4ec0\u4e48\u60c5\u51b5\u4e0b\u63d2\u5165<\/em><\/strong><\/p>\n\n\n\n
class Solution {\npublic:\n    void travseral(TreeNode *cur, int val) {\n        if(cur->val < val) {\n            if(cur->right) travseral(cur->right, val);\n            else {\n                cur->right = new TreeNode(val);\n                return ;\n            }\n        }\n        if(cur->val > val) {\n            if(cur->left) travseral(cur->left, val);\n            else {\n                cur->left = new TreeNode(val);\n                return ;\n            }\n        }\n    }\n    TreeNode* insertIntoBST(TreeNode* root, int val) {\n        if(!root) return new TreeNode(val);\n        travseral(root, val);\n        return root;\n    }\n};<\/code><\/pre>\n\n\n\n
\n\n\n\n
669. \u4fee\u526a\u4e8c\u53c9\u641c\u7d22\u6811<\/a>\u274c<\/h2>\n\n\n\n
\u601d\u8def\u6709\u70b9\u96be\u60f3 \u600e\u4e48\u5b9e\u73b0\u7684\u8282\u70b9\u79fb\u9664 \u600e\u4e48\u63a5\u4f4f\u8fd4\u56de\u7684\u8282\u70b9<\/strong><\/em><\/p>\n\n\n\n
class Solution {\npublic:\n    TreeNode* trimBST(TreeNode* cur, int low, int high) {\n        if(!cur) return nullptr;\n\n        if(cur->val > high) { \/\/\u8d85\u51fa\u4e0a\u9650 \u53bb\u5de6\u8fb9\u627e\u7b26\u5408\u533a\u95f4\u7684\u5b50\u6811\u6765\u66ff\u4ee3cur\n            return trimBST(cur->left, low, high);\n        }\n        if(cur->val < low) { \/\/\u4f4e\u4e8e\u4e0b\u9650 \u53bb\u53f3\u8fb9\u627e\u7b26\u5408\u533a\u95f4\u7684\u5b50\u6811\u6765\u66ff\u4ee3cur\n            return trimBST(cur->right, low, high);\n        }\n\n        cur->left = trimBST(cur->left, low, high); \/\/\u63a5\u4f4f\u4e0b\u4e00\u5c42\u7b26\u5408\u533a\u95f4\u7684\u5b50\u6811\n        cur->right = trimBST(cur->right, low, high);\n\n        return cur;\n    }\n}; <\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
More content\uff1aLeetCode hot100@\u4e8c\u53c9\u6811 257. \u4e8c\u53c9\u6811\u7684\u6240\u6709\u8def\u5f84\u274c \u9012\u5f52\u56de\u6eaf \u9012\u5f52 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[27,18,48,19],"class_list":["post-1177","post","type-post","status-publish","format-standard","hentry","category-suanfa","tag-c","tag-leetcode","tag-48","tag-19"],"_links":{"self":[{"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/posts\/1177","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/guapicoding.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1177"}],"version-history":[{"count":37,"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/posts\/1177\/revisions"}],"predecessor-version":[{"id":2321,"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/posts\/1177\/revisions\/2321"}],"wp:attachment":[{"href":"https:\/\/guapicoding.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1177"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/guapicoding.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1177"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/guapicoding.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1177"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}