算法训练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;
        }
    };