654. 最大二叉树

第一想法

和LC105, 106一样, 但是逻辑更加简单,直接采用传index;

看完题解后的想法

–

实现中遇到的困难

注意index是全局index所以直接传

代码

class Solution {
public:
    TreeNode* recurse(vector<int>& nums, int begin, int end) {
        if (begin == end) return nullptr;

        // 1. 找到max值和index，这就是root
        int indexRoot = begin;
        for (int i = begin; i < end; i++) {
            if (nums[i] > nums[indexRoot]) {
                indexRoot = i;
            }
        }
        TreeNode* root = new TreeNode(nums[indexRoot]);

        // 2. 挂树+直接传index做分组，注意index是全局index所以直接传
        root->left = recurse(nums, begin, indexRoot);
        root->right = recurse(nums, indexRoot+1, end);

        return root;
    }
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return recurse(nums, 0, (int)nums.size());
    }
};

617. 合并二叉树

第一想法

使用递归， 返回 root1 ， 只要 root1 没有某棵树， 就挂上 root2 的；

看完题解后的想法

可以简化：核心逻辑就是

if (!root1) return root2;
if (!root2) return root1;

如果root1没有，就返回root2（挂上），如果root2没有，那直接返回root1；

实现中遇到的困难

–

代码

简化版：

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;
    }
};

自己写的复杂版：

class Solution {
public:
    void dfs(TreeNode* root1, TreeNode* root2) {
        if (!root2) return;

        root1->val = root1->val + root2->val;

        if (!root1->left) {
            root1->left = root2->left;
        } else {
            dfs(root1->left, root2->left);
        }

        if (!root1->right) {
            root1->right = root2->right;
        } else {
            dfs(root1->right, root2->right);
        }
    }

    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if (!root1) return root2;
        if (!root2) return root1;
        dfs(root1, root2);
        return root1;
    }
};

700. 二叉搜索树中的搜索

第一想法

利用二叉搜索树的性质进行大小判断；

看完题解后的想法

利用二叉搜索树的性质直接进行迭代更简单，不用额外的空间，直接跑；

实现中遇到的困难

–

代码

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        while (root) {
            if (root->val == val) {
                return root;
            } else if (root->val > val) {
                root = root->left;
            } else {
                root = root->right;
            }
        }

        return nullptr;
    }
};

98. 验证二叉搜索树

第一想法

利用中序遍历 左 - 根 - 右 进行比较；

看完题解后的想法

可以转换为一个序列，但是递归可以直接做，只是要多一个全局变量用作记录上一个值；

实现中遇到的困难

–

代码

class Solution {
public:
    long long prev = LLONG_MIN;

    bool isValidBST(TreeNode* root) {
        if (!root) {
            return true;
        }

        bool left = isValidBST(root->left);

        if (root->val <= prev) {
            return false;
        }
        prev = root->val;

        bool right = isValidBST(root->right);

        return left && right;
    }
};

今日收获