算法训练day20 LeetCode654.617.700.98

654.最大二叉树

题目

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

题解

代码随想录 (programmercarl.com)

使用递归
- 返回节点地址，输入父节点地址，数组
- 终止条件是输入地数组为空
- 单层操作：
  - 如果输入数组为空，则返回父节点地址
  - 否则找到数组中最大值、分割数组，对最大值进行操作、将新的两个数组送入深一层递归函数。
修改
- 输入数组，返回节点
- 结束条件数组大小为1
- 单层递归逻辑不变

代码：

class Solution
{
public:
    TreeNode *constructMaximumBinaryTree(vector<int> &nums)
    {
        TreeNode *node = new TreeNode(0);
        if (nums.size() == 1)
        {
            node->val = nums[0];
            return node;
        }

        int maxValue = 0;
        int maxValueIndex = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            if (nums[i] > maxValue)
            {
                maxValue = nums[i];
                maxValueIndex = i;
            }
        }
        node->val = maxValue;

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

整体思路没有问题，细节实现需要加强

617.合并二叉树

题目

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

题解

代码随想录 (programmercarl.com)

使用层序遍历
- 对两个树同时进行层序遍历，遍历时对比节点，在同一节点至少有一棵树存在时将节点记录，空则用NULL标记，记录在两个队列中
- 对比队列，构建新树
修正
- 一边遍历一遍更改
- 通过使用地址的方式实现空位置安装子数

代码:

class Solution
{
public:
    TreeNode *mergeTrees(TreeNode *root1, TreeNode *root2)
    {
        if (root1 == NULL)
            return root2;
        if (root2 == NULL)
            return root1;
        queue<TreeNode *> que;
        que.push(root1);
        que.push(root2);
        while (!que.empty())
        {
            TreeNode *node1 = que.front();
            que.pop();
            TreeNode *node2 = que.front();
            que.pop();

            node1->val += node2->val;

            if (node1->left != NULL && node2->left != NULL)
            {
                que.push(node1->left);
                que.push(node2->left);
            }
            if (node1->right != NULL && node2->right != NULL)
            {
                que.push(node1->right);
                que.push(node2->right);
            }

            if (node1->left == NULL && node2->left != NULL)
            {
                node1->left = node2->left;
            }
            if (node1->right == NULL && node2->right != NULL)
            {
                node1->right = node2->right;
            }
        }
        return root1;
    }
};

700.二叉搜索树中的搜索

题目

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

题解

代码随想录 (programmercarl.com)

搜索树中对于每一根节点，左子树中所有节点值一定均小于根节点的值，右子树中所有节点值一定均大于根节点的值

class Solution
{
public:
    TreeNode *searchBST(TreeNode *root, int val)
    {
        if (root == NULL || root->val == val)
            return root;
        TreeNode *result = NULL;
        if (root->val > val)
            result = searchBST(root->left, val);
        if (root->val < val)
            result = searchBST(root->right, val);
        return result;
    }
};

98.验证二叉搜索树

题目

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

题解

代码随想录 (programmercarl.com)

递归的方式，只需要判断根节点的两个子节点是否满足二叉搜索树的条件
修正：
- 局部满足条件不一定全局满足条件

平衡二叉树使用中序遍历结果是递增数列

将树经中序遍历转换成数组，判断数组是否递增

class Solution
{
private:
    vector<int> vec;
    void traversal(TreeNode *root)
    {
        if (root == NULL)
            return;
        traversal(root->left);
        vec.push_back(root->val);
        traversal(root->right);
    }

public:
    bool isValidBST(TreeNode *root)
    {
        vec.clear();
        traversal(root);
        for (int i = 1; i < vec.size(); i++)
        {
            if (vec[i] <= vec[i - 1])
                return false;
        }
        return true;
    }
};

递归

class Solution
{
public:
    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;
    }
};