ZklMao-Space
large picture of the cover

算法日记 - 二叉树

LC 144. 二叉树的前序遍历：https://leetcode.cn/problems/binary-tree-preorder-traversal/

144. 二叉树的前序遍历 - 力扣（LeetCode）

/**
 * 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<int> ret;
    vector<int> preorderTraversal(TreeNode* root) {
        if (!root) return ret;
        ret.push_back(root->val);
        if (root->left) preorderTraversal(root->left);
        if (root->right) preorderTraversal(root->right);
        return ret;  
    }
};

LC 94. 二叉树的中序遍历：https://leetcode.cn/problems/binary-tree-inorder-traversal/

94. 二叉树的中序遍历 - 力扣（LeetCode）

class Solution {
public:
    vector<int> ret;
    vector<int> inorderTraversal(TreeNode* root) {
        if (!root) return ret;
        if (root->left) inorderTraversal(root->left);
        ret.push_back(root->val);
        if (root->right) inorderTraversal(root->right);
        return ret;  
    }
};

LC 145. 二叉树的后序遍历：https://leetcode.cn/problems/binary-tree-postorder-traversal/

145. 二叉树的后序遍历 - 力扣（LeetCode）

class Solution {
public:
    vector<int> ret;
    vector<int> postorderTraversal(TreeNode* root) {
        if (!root) return ret;
        if (root->left) postorderTraversal(root->left);
        if (root->right) postorderTraversal(root->right);
        ret.push_back(root->val);
        return ret;  
    }
};

LC 102.二叉树的层序遍历：https://leetcode.cn/problems/binary-tree-level-order-traversal/

102. 二叉树的层序遍历 - 力扣（LeetCode）

class Solution {
public:

    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ret;
        if (!root) return ret;
        queue<TreeNode*>VisitQue;
        queue<TreeNode*>tQue;
        VisitQue.push(root);
        ret.emplace_back(vector<int>(1,root->val));
        while (!VisitQue.empty())
        {
            // [1,2,3,4,null,null,5] 注意这个测试用例
            vector<int> LevelVal;
            while(!VisitQue.empty())
            {
                //  vector<int> LevelVal;写这里不行
                // 会错误输出 [[1],[2,3],[4],[5]], 正确输出是 [[1],[2,3],[4,5]]
                if (VisitQue.front()->left)
                {
                    LevelVal.push_back(VisitQue.front()->left->val);
                    tQue.push(VisitQue.front()->left);
                }
                if (VisitQue.front()->right)
                {
                    LevelVal.push_back(VisitQue.front()->right->val);
                    tQue.push(VisitQue.front()->right);
                }
                VisitQue.pop();
            }
            // [1,2,3,4,null,null,5] 注意这个测试用例
            // [1,2,3,4,null,null,5] 注意这个测试用例
            if (!LevelVal.empty())
                ret.emplace_back(LevelVal);
            while (!tQue.empty())
            {
                VisitQue.push(tQue.front());
                tQue.pop();                
            }    
        }
        ret.shrink_to_fit();
        return ret;
    }
};

LC 226.翻转二叉树：https://leetcode.cn/problems/invert-binary-tree/

226. 翻转二叉树 - 力扣（LeetCode）

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) return root;
        swap(root->left, root->right);
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};

LC 101. 对称二叉树：https://leetcode.cn/problems/symmetric-tree/

101. 对称二叉树 - 力扣（LeetCode）

/**
 * 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:
    bool compareNode(TreeNode* left,TreeNode* right){
        if (!left && right) return false;
        else if(left && !right) return false;
        else if (!left && !right) return true;
        else if (left->val != right->val) return false;

        bool outsideNodeCmpRes = compareNode(left->left,right->right);
        bool innerNodeCmpRes = compareNode(left->right,right->left);
        bool isSymmetry = outsideNodeCmpRes && innerNodeCmpRes;
        return isSymmetry;
    }
    bool isSymmetric(TreeNode* root) {
        if (!root) return true;
        return compareNode(root->left,root->right);
    }
};

LC 104.二叉树的最大深度：https://leetcode.cn/problems/maximum-depth-of-binary-tree/

104. 二叉树的最大深度 - 力扣（LeetCode）

/**
 * 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:
    int getDepth(TreeNode* node){
        if (!node) return 0;
        int leftPathDepth = getDepth(node->left);
        int rightPathDepth = getDepth(node->right);
        int depth = 1+max(leftPathDepth,rightPathDepth);
        return depth;
    }
    int maxDepth(TreeNode* root) {
        if (!root) return 0;
        return getDepth(root);
    }
};

LC 111.二叉树的最小深度：https://leetcode.cn/problems/minimum-depth-of-binary-tree/

111. 二叉树的最小深度 - 力扣（LeetCode）

/**
 * 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:
    int minDepth(TreeNode* root) {
        if (!root) return 0;
        if (root->left && !root->right)
            return 1+minDepth(root->left);
        if (!root->left && root->right)
            return 1+minDepth(root->right);
        return 1 + min(minDepth(root->left),minDepth(root->right));
    }
};

LC 222.完全二叉树的节点个数：https://leetcode.cn/problems/count-complete-tree-nodes/

222. 完全二叉树的节点个数 - 力扣（LeetCode）

/**
 * 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:
    int getNodeSum(TreeNode* node){
       if (!node) return 0;
       int leftNodeSum =  getNodeSum(node->left);
       int rightNodeSum = getNodeSum(node->right);
       return (leftNodeSum + rightNodeSum + 1); 
    }
    int countNodes(TreeNode* root) {
        if (!root) return 0;
        if (!root->left && !root->right) return 1;
        return getNodeSum(root);
    }
};

LC 110.平衡二叉树：https://leetcode.cn/problems/balanced-binary-tree/

110. 平衡二叉树 - 力扣（LeetCode）

/**
 * 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:
    int getHight(TreeNode* node){
        if (!node) return 0;
        int leftHight = getHight(node->left);
        if (leftHight == -1) return -1;
        int rightHight = getHight(node->right);
        if (rightHight == -1) return -1;
        if (abs(leftHight - rightHight) > 1) return -1;
        return (1+max(leftHight , rightHight));         
    }
    bool isBalanced(TreeNode* root) {
        if (!root) return true;
        return getHight(root) == -1 ? false : true;
    }
};

LC 257. 二叉树的所有路径：https://leetcode.cn/problems/binary-tree-paths/

257. 二叉树的所有路径 - 力扣（LeetCode）

/**
 * 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:
    void traversalTree(TreeNode* node, string path, vector<string>& res){
        path += to_string(node->val);
        if (!node->left && !node->right){
            res.emplace_back(path);
            return;
        } 
        if (node->left) traversalTree(node->left,path + "->", res);
        if (node->right) traversalTree(node->right,path + "->", res);        
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        if (!root) return res;
        string path;
        traversalTree(root,path,res);
        res.shrink_to_fit();
        return res;
    }
};

LC 404.左叶子之和：https://leetcode.cn/problems/sum-of-left-leaves/

404. 左叶子之和 - 力扣（LeetCode）

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

LC 513.找树左下角的值：https://leetcode.cn/problems/find-bottom-left-tree-value/

513. 找树左下角的值 - 力扣（LeetCode）

/**
 * 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:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> que;
        que.push(root);
        int resVal = 0, size;
        TreeNode* tNode;
        while(!que.empty()){
            size = que.size();
            for (int i = 0; i < size; ++ i){
                tNode = que.front();
                que.pop();
                if (i == 0) resVal = tNode->val;
                if (tNode->left) que.push(tNode->left);
                if (tNode->right) que.push(tNode->right);
            }
        }
        return resVal;
    }
};

LC 112. 路径总和：https://leetcode.cn/problems/path-sum/

112. 路径总和 - 力扣（LeetCode）

/**
 * 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:
    bool traversal(TreeNode* node,int sum){
        if (!node->left && !node->right && sum == 0) return true;
        else if (!node->left && !node->right && sum != 0) return false;
        if (node->left){
            if(traversal(node->left,sum-=node->left->val)) return true;
            sum += node->left->val;
        }
        if (node->right){
            if(traversal(node->right,sum-=node->right->val)) return true;
            sum += node->right->val;
        }
        return false;
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (!root) return false;
        return traversal(root,targetSum - root->val);
    }
};

LC 106.从中序与后序遍历序列构造二叉树：https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）

/**
 * 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:
    TreeNode* traversal(vector<int>& inorder, vector<int>& postorder){
        if (!postorder.size()) return nullptr;
        
        int rootVal = postorder[postorder.size() - 1];
        TreeNode* root = new TreeNode(rootVal);
        
        if (postorder.size() == 1) return root;

        int delimitInx;
        for (delimitInx = 0; delimitInx < inorder.size(); ++ delimitInx){
            if (inorder[delimitInx] == rootVal) break;
        }

        vector<int> leftIndeor(inorder.begin(),inorder.begin() + delimitInx);
        vector<int> rightIndeor(inorder.begin() + delimitInx + 1,inorder.end());

        postorder.resize(postorder.size() - 1);

        vector<int> leftPostOrder(postorder.begin(), postorder.begin() + leftIndeor.size());
        vector<int> rightPostOrder(postorder.begin() + leftIndeor.size(),postorder.end());

        root->left = traversal(leftIndeor,leftPostOrder);
        root->right = traversal(rightIndeor,rightPostOrder);
        return root;        
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.size() == 1 && postorder.size() == 1) return new TreeNode(inorder[0]);
        return traversal(inorder,postorder);
    }
};

LC 654.最大二叉树：https://leetcode.cn/problems/maximum-binary-tree/

654. 最大二叉树 - 力扣（LeetCode）

/**
 * 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:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        TreeNode* node = new TreeNode(0);
        if (nums.size() == 1){
            node->val = nums[0];
            return node;
        }
        
        int maxVal = 0,maxValInx = 0;
        for(int i = 0; i < nums.size(); ++ i){
            if (maxVal < nums[i])
            {
                maxVal = nums[i];
                maxValInx = i;
            }
        }
        node->val = maxVal;

        if (maxValInx > 0){
            vector<int> newVec(nums.begin(),nums.begin() + maxValInx);
            node->left = constructMaximumBinaryTree(newVec);
        }

        if (maxValInx < nums.size() - 1){
            vector<int> newVec(nums.begin() + maxValInx + 1,nums.end());
            node->right = constructMaximumBinaryTree(newVec);
        }
        return node;
    }
};

LC 617.合并二叉树：https://leetcode.cn/problems/merge-two-binary-trees/

617. 合并二叉树 - 力扣（LeetCode）

/**
 * 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:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if (!root1) return root2;
        if (!root2) return root1;
        root1->val += root2->val;
        root1->left = mergeTrees(root1->left,root2->left);
        root1->right = mergeTrees(root1->right,root2->right);
        return root1;
    }
};

LC 700.二叉搜索树中的搜索：https://leetcode.cn/problems/search-in-a-binary-search-tree/

700. 二叉搜索树中的搜索 - 力扣（LeetCode）

  • 递归


/**
 * 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:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (!root) return nullptr;
        if (root->val == val) return root;
        TreeNode* tNode;
        if (root->val < val) tNode = searchBST(root->right,val);
        if (root->val > val) tNode = searchBST(root->left,val);        
        return tNode;
    }
};

  • 迭代

/**
 * 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:
    TreeNode* searchBST(TreeNode* root, int val) {
        while (root != NULL) {
            if (root->val > val) root = root->left;
            else if (root->val < val) root = root->right;
            else return root;
        }
        return NULL;
    }
};

LC 98.验证二叉搜索树：https://leetcode.cn/problems/validate-binary-search-tree/

98. 验证二叉搜索树 - 力扣（LeetCode）

/**
 * 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:
    long long maxVal = LONG_MIN;
    bool isValidBST(TreeNode* root) {
        if (!root) return true;
        bool leftValid = isValidBST(root->left);
        if (maxVal < root->val) maxVal = root->val;
        else return false;
        bool rightvalid = isValidBST(root->right);
        return leftValid && rightvalid;
    }
};

LC 530.二叉搜索树的最小绝对差：https://leetcode.cn/problems/minimum-absolute-difference-in-bst/

530. 二叉搜索树的最小绝对差 - 力扣（LeetCode）

/**
 * 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:
    int minAbsSub = INT_MAX;
    TreeNode* preNode;
    void traversal(TreeNode* root){
        if (!root) return;
        traversal(root->left);
        if(preNode) minAbsSub = min(minAbsSub,root->val - preNode->val);
        preNode = root;
        traversal(root->right);
    }

    int getMinimumDifference(TreeNode* root) {
        traversal(root);
        return minAbsSub;
    }
};

LC 501.二叉搜索树中的众数：https://leetcode.cn/problems/find-mode-in-binary-search-tree/

501. 二叉搜索树中的众数 - 力扣（LeetCode）

/**
 * 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:
    int maxCount = 0,count = 0;
    TreeNode* preNode;
    vector<int> res;
    void traversal(TreeNode* node){
        if (!node) return;
        traversal(node->left);
        if(!preNode) count = 1;
        else if (preNode->val == node->val) count ++;
        else count = 1;
        preNode = node;

        if (count == maxCount) res.emplace_back(node->val);
        else if (count > maxCount) {
            res.clear();
            maxCount = count;
            res.emplace_back(node->val);
        }
        traversal(node->right);
    }
    vector<int> findMode(TreeNode* root) {
        traversal(root);
        res.shrink_to_fit();
        return res;
    }
};

LC 236. 二叉树的最近公共祖先：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/

236. 二叉树的最近公共祖先 - 力扣（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) return nullptr;
        if (root == p || root == q) return root;
        TreeNode* leftNode = lowestCommonAncestor(root->left,p,q);
        TreeNode* rightNode = lowestCommonAncestor(root->right,p,q);       
        
        if (leftNode && rightNode) return root;
        else if (leftNode && !rightNode) return leftNode;
        else if (!leftNode && rightNode) return rightNode;
        else return nullptr;
    }
};

LC 235. 二叉搜索树的最近公共祖先：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/

235. 二叉搜索树的最近公共祖先 - 力扣（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->val > p->val && root->val > q->val)
            return lowestCommonAncestor(root->left,p,q);
        else if (root->val < p->val && root->val < q->val)
            return lowestCommonAncestor(root->right,p,q);
        else return root;
    }
};

LC 701.二叉搜索树中的插入操作：https://leetcode.cn/problems/insert-into-a-binary-search-tree/

701. 二叉搜索树中的插入操作 - 力扣（LeetCode）

/**
 * 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:
    TreeNode *parent;
    void traversal(TreeNode* root,int val){
        if (!root){
            TreeNode* node = new TreeNode(val);
            if (parent->val < val) parent->right = node;
            else if (parent->val > val) parent->left = node;
            return;
        }
        parent = root;
        
        if (parent->val < val) traversal(root->right,val);
        else if (parent->val > val) traversal(root->left,val);
        return;
    }
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (!root){
            root = new TreeNode(val);
            return root;
        }
        traversal(root,val);
        return root;
    }
};

LC 450.删除二叉搜索树中的节点：https://leetcode.cn/problems/delete-node-in-a-bst/

450. 删除二叉搜索树中的节点 - 力扣（LeetCode）

/**
 * 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:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (!root) return root;
        if (root->val == key){
            if (!root->left && !root->right){
                delete root;
                return nullptr;
            }else if (!root->left && root->right){
                auto retNode = root->right;
                delete root;
                return retNode;
            }else if (root->left && !root->right){
                auto retNode = root->left;
                delete root;
                return retNode;
            } else if (root->left && root->right){
                TreeNode* cur = root->right;
                while (cur->left){
                    cur = cur->left;
                }
                cur->left = root->left;
                TreeNode* tmp = root;
                root = root->right;
                delete tmp;
                return root;
            }
        }
        if (root->val < key) root->right = deleteNode(root->right,key);
        if (root->val > key) root->left = deleteNode(root->left,key);
        return root;
    }
};

LC 669. 修剪二叉搜索树：https://leetcode.cn/problems/trim-a-binary-search-tree/

669. 修剪二叉搜索树 - 力扣（LeetCode）

/**
 * 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:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if (!root) return root;
        if (root->val < low){
            TreeNode* rightNode = trimBST(root->right,low,high);
            return rightNode;
        }
        if (root->val > high){
            TreeNode* leftNode = trimBST(root->left,low,high);
            return leftNode;
        }
        root->left = trimBST(root->left,low,high);
        root->right = trimBST(root->right,low,high);        
        return root;
    }
};

LC 108.将有序数组转换为二叉搜索树：https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/

108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）

/**
 * 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:
    TreeNode* traversal(vector<int> & nums,int left,int right){
        if (left > right) return nullptr;
        int mid = (left + right) >> 1;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = traversal(nums,left,mid-1);
        root->right = traversal(nums,mid+1,right);
        return root;     
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        TreeNode *root = traversal(nums,0,nums.size() -1);
        return root;
    }
};

LC 538.把二叉搜索树转换为累加树：https://leetcode.cn/problems/convert-bst-to-greater-tree/

538. 把二叉搜索树转换为累加树 - 力扣（LeetCode）

/**
 * 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:
    int PreSumVal = 0;
    void traversal(TreeNode* node){
        if (!node) return;
        traversal(node->right);
        node->val += PreSumVal;
        PreSumVal = node->val;
        traversal(node->left);
    }
    TreeNode* convertBST(TreeNode* root) {
        if (!root) return root;
        traversal(root);
        return root;
    }
};

site logo

And if we

© 2025 ZklMao-Space