算法随想Day18【二叉树】| LC654-最大二叉树、LC617-合并二叉树、LC700-二叉搜索树中的搜索、LC98-验证二叉搜索树

LC654. 最大二叉树

内存消耗只击败10%

TreeNode* buildTree(vector<int> nums)
{
    int max = nums[0];
    int index = 0;
    for (int i = 1; i < nums.size(); i++)
    {
        if (nums[i] > max)
        {
            max = nums[i];
            index = i;
        }
    }
    TreeNode* root = new TreeNode(max);
    if (index != 0)
        root->left = buildTree(vector<int>(nums.begin(), nums.begin() + index));
    if (index != nums.size() - 1)
        root->right  = buildTree(vector<int>(nums.begin() + index + 1, nums.end()));
    return root;
}

TreeNode* constructMaximumBinaryTree(vector<int>& nums)
{
    return buildTree(nums);
}

内存改进版本：

// 在左闭右开区间[left, right)，构造二叉树
TreeNode* traversal(vector<int>& nums, int left, int right) {
    if (left >= right) return nullptr;

    // 分割点下标：maxValueIndex
    int maxValueIndex = left;
    for (int i = left + 1; i < right; ++i) {
        if (nums[i] > nums[maxValueIndex]) maxValueIndex = i;
    }

    TreeNode* root = new TreeNode(nums[maxValueIndex]);

    // 左闭右开：[left, maxValueIndex)
    root->left = traversal(nums, left, maxValueIndex);

    // 左闭右开：[maxValueIndex + 1, right)
    root->right = traversal(nums, maxValueIndex + 1, right);

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

上面的代码看上去简洁一些，主要是因为第二版其实是允许空节点进入递归，所以不用在递归的时候加判断节点是否为空（如if (index != 0) 和 if (index != nums.size() - 1)）

单调栈思路(题解链接)：

https://leetcode.cn/problems/maximum-binary-tree/solution/zhua-wa-mou-si-by-muse-77-myd7/

采用单调栈的基本思路是这样的：

1. 如果栈顶元素大于待插入的元素，那么直接入栈。
2. 如果栈顶元素小于待插入的元素，那么栈顶元素出栈。

当然，在对比两个节点大小和出入栈的同时，依然还是会根据题意，进行二叉树的构造。即：

1. 如果栈顶元素大于待插入的元素，则：栈顶元素.right = 待插入元素。
2. 如果栈顶元素小于待插入的元素，则：待插入元素.left = 栈顶元素。

LC617. 合并二叉树

TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2)
{
    if (root1 == nullptr) return root2;
    if (root2 == nullptr) return root1;
    TreeNode* root = root1;
    root->val = root1->val + root2->val;
    root->left = mergeTrees(root1->left, root2->left);
    root->right = mergeTrees(root1->right, root2->right);
    return root;
}

LC700. 二叉搜索树中的搜索

递归版本：

private:
TreeNode* search_result;
void searchBSTLoop(TreeNode* root, int& val)
{
    if (root == nullptr || search_result != nullptr)
    {
        return;
    }
    if (root->val == val)
        search_result = root;
    else if (root->val > val)
        searchBST(root->left, val);
    else
        searchBST(root->right, val);
}
public:
TreeNode* searchBST(TreeNode* root, int val)
{
    search_result = nullptr;
    searchBSTLoop(root, val);
    return search_result;
}

迭代版本：

TreeNode* searchBST(TreeNode* root, int val)
{
    TreeNode* curr = nullptr;
    TreeNode* search_result = nullptr;
    if (root != nullptr)
    {
        curr = root;
    }
    while (curr != nullptr)在·
    {
        if (curr->val == val)
        {
            search_result = curr;
            break;
        }
        else if (curr->val > val)
            curr = curr->left;
        else
            curr = curr->right;
    }
    return search_result;
}

LC98. 验证二叉搜索树

暴力解法：

中序遍历搜集为一个数组，逐个验证是否为单调递增

////vector数组搜集，再逐个比较，内存消耗大
void inOrderTravesal(TreeNode* root, vector<int>& result)
{
    if (root == nullptr)
    {
        return;
    }
    inOrderTravesal(root->left, result);
    result.push_back(root->val);
    inOrderTravesal(root->right, result);
}
bool isValidBST(TreeNode* root)
{
    if (root == nullptr)
    {
        return true;
    }
    vector<int> result;
    inOrderTravesal(root, result);
    for (int i = 1; i < result.size(); i++)
    {
        if (result[i] <= result[i - 1])
            return false;
    }
    return true;
}

自实现用遍历搞的一版

////中序遍历的遍历都写出来了，咋没想到搞个递归呢
bool isValidBST_V2(TreeNode* root)
{
    long long temp = LONG_LONG_MIN;
    bool flag = true;
    TreeNode* curr = nullptr;
    if (root != nullptr)
    {
        curr = root;
    }
    stack<TreeNode*> sta;
    while (curr != nullptr || sta.empty() != true)
    {
        if (curr != nullptr)
        {
            sta.push(curr);
            curr = curr->left;
        }
        else
        {
            curr = sta.top();
            if (curr->val <= temp)
            {
                flag = false;
                break;
            }
            temp = curr->val;
            sta.pop();
            curr = curr->right;
        }
    }
    return flag;
}

开始尝试用递归解题，想得太复杂，而且也踩坑了

[5,4,6,null,null,3,7] 情况下通过不了

bool flag;
int checkValidBST(TreeNode* root, int is_left, int val)
{
    if (root == nullptr)
        return INT_MIN;
    int temp = INT_MIN;
    if (root->left != nullptr)
        temp = checkValidBST(root->left, 1, root->val);
    ////这两个if是想多了，而且为什么没想到跟上面遍历做法一样用一个
    ////TreeNode* prev或者long long temp去记录前面访问过的
    if (root->val <= temp)
        flag = false;
    if (is_left == 0 && root->val <= val)
        flag = false;
    checkValidBST(root->right, 0, root->val);
    return root->val;
}
bool isValidBST(TreeNode* root)
{
    flag = true;
    if (root == nullptr)
        return false;
    checkValidBST(root, -1, root->val);
    return flag;
}

后续看了讲解，写了一版

////递归的两种思路
////1、用一个变量更新当前遇到的最大值
////2、用一个prev指针指向刚访问完的节点
////这里采用第二种试下
bool flag;
TreeNode* prev = nullptr;
void isValidBSTLoop(TreeNode* root)
{
    if (root == nullptr)
    {
        return;
    }
    isValidBSTLoop(root->left);
    if (prev != nullptr && root->val <= prev->val)
    {
        flag =  false;
    }
    prev = root;
    isValidBSTLoop(root->right);
}
bool isValidBST(TreeNode* root)
{
    flag = true;
    isValidBSTLoop(root);
    return flag;
}

Carl哥题解对返回值的处理更加简洁、巧妙：

return left && right：当整棵树中有一个节点不满足，通过与运算最后返回的都会是false

TreeNode* pre = NULL; // 用来记录前一个节点
bool isValidBST(TreeNode* root) {
    if (root == NULL) return true;
    bool left = isValidBST(root->left);

    if (pre != NULL && pre->val >= root->val) return false;
    pre = root; // 记录前一个节点

    bool right = isValidBST(root->right);
    return left && right;
}