leetcode习题集【8月】

二叉树相关

617. 合并二叉树

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        // 第一步 确定递归函数的参数和返回值
            //首先合入两个二叉树 参数至少是传入两个二叉树的根节点 返回值就是合并之后二叉树的根节点 
        // 第二步 确定终止条件
            // 传入两个数 那么就有两个数遍历的节点t1 和 t2
        if(root1 == NULL) return root2;
        if(root2 == NULL) return root1;
        // 第三步 确定单层递归的逻辑 
            // 单层递归中 就是把两棵树的元素加到一起
        root1 -> val += root2 -> val;

        // 第四步 递归 合并t1左子树 t2左子树 之后的左子树
            //t1 的右子树 就是合并t1右子树 t2 右子树之后的右子树
            // 最终t1就是合并之后的根节点
        root1 -> left = mergeTrees(root1 -> left, root2 -> left);
        root1 -> right = mergeTrees(root1 -> right, root2 -> right);
        return root1; 

    }
};

700. 二叉搜索树中的搜索

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        // 确定终止条件
        if(root == NULL || root -> val == val) return root;

        // 确定单层递归的逻辑 也就是说 根节点的值大于或者小于 val 的值 那就去其他的地方找
        // 同时可以确认的是 我们确定的值是一个结点 而不是一个数值
        TreeNode* result = NULL;
        if(root -> val > val) result = searchBST(root -> left, val);
        if(root -> val < val) result = searchBST(root -> right,val);
        return result;
    }
};

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

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 终止条件
        if(root == q || root == p || root == NULL) return root;
        // 确定单层递归逻辑
        TreeNode* left = lowestCommonAncestor(root -> left, p, q);
        TreeNode* right = lowestCommonAncestor(root -> right , p, q);
        if(left != NULL && right != NULL)  return root ;


        if(left == NULL && right != NULL) return right;
        else if(left != NULL && right == NULL) return left;
        else{
            return NULL;
        }  

        
    }
};

701. 二叉搜索树中的插入操作

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        // 思路： 遍历二叉搜索树， 找到空节点 插入元素就可以了 
        //如果是 根节点是空值 那么可以创建节点 返回创建的节点就可以了
        // 如果root 节点 > 当前值 直接返回递归点 右边也是一样
        if(root == NULL) {
            TreeNode* node = new TreeNode(val);
            return node;
        }
        if(root -> val > val) root -> left = insertIntoBST(root -> left, val);
        if(root -> val < val) root -> right = insertIntoBST(root -> right, val);

    }
};

108. 将有序数组转换为二叉搜索树

class Solution {
private:
    TreeNode* traversal(vector<int>& num, int left, int right){
        // 确定函数终止条件
        if(left > right) return nullptr;
        // 确定单层递归的逻辑
        int mid = left + (right - left) / 2;
        TreeNode* root = new TreeNode(num[mid]);
        root -> left = traversal(num, left, mid - 1);
        root -> right = traversal(num, mid + 1, right);
        return root;
    }
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        TreeNode* root = traversal(nums, 0 , nums.size() - 1);
        return root;

    }
};

538. 把二叉搜索树转换为累加树

class Solution {
private:
    int pre = 0;
    void traversal(TreeNode* cur){
        if(cur == NULL) return ;
        traversal(cur -> right);
        cur -> val += pre;
        pre = cur -> val;
        traversal(cur -> left);

    }

public:
    TreeNode* convertBST(TreeNode* root) {
        pre = 0;
        traversal(root);
        return root;

    }
};