首页 > 其他分享 >代码随想录打卡Day17

代码随想录打卡Day17

时间:2024-11-05 22:49:16浏览次数:4  
标签:right TreeNode val 随想录 Day17 打卡 root 节点 left

1.力扣954:最大二叉树:

题目描述:

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

  1. 创建一个根节点,其值为 nums 中的最大值。
  2. 递归地在最大值 左边 的 子数组前缀上 构建左子树。
  3. 递归地在最大值 右边 的 子数组后缀上 构建右子树。

返回 nums 构建的 最大二叉树 

示例 1:

输入:nums = [3,2,1,6,0,5]
输出:[6,3,5,null,2,0,null,null,1]
解释:递归调用如下所示:
- [3,2,1,6,0,5] 中的最大值是 6 ,左边部分是 [3,2,1] ,右边部分是 [0,5] 。
    - [3,2,1] 中的最大值是 3 ,左边部分是 [] ,右边部分是 [2,1] 。
        - 空数组,无子节点。
        - [2,1] 中的最大值是 2 ,左边部分是 [] ,右边部分是 [1] 。
            - 空数组,无子节点。
            - 只有一个元素,所以子节点是一个值为 1 的节点。
    - [0,5] 中的最大值是 5 ,左边部分是 [0] ,右边部分是 [] 。
        - 只有一个元素,所以子节点是一个值为 0 的节点。
        - 空数组,无子节点。

示例 2:

输入:nums = [3,2,1]
输出:[3,null,2,null,1]

解答代码:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
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;
    }

};

2.力扣617:合并二叉树:

题目描述:

给你两棵二叉树: root1 和 root2 。

想象一下,当你将其中一棵覆盖到另一棵之上时,两棵树上的一些节点将会重叠(而另一些不会)。你需要将这两棵树合并成一棵新二叉树。合并的规则是:如果两个节点重叠,那么将这两个节点的值相加作为合并后节点的新值;否则,不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

示例 1:

输入:root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出:[3,4,5,5,4,null,7]

示例 2:

输入:root1 = [1], root2 = [1,2]
输出:[2,2]

解答代码:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if (root1 == NULL) return root2;
        if (root2 == NULL) return root1;

        // 前序遍历

        root1->val += root2->val;

        root1->left = mergeTrees(root1->left, root2->left);
        root1->right = mergeTrees(root1->right, root2->right);

        return root1;
    }
};

3.力扣700:二叉树搜索树中的搜索:

题目描述:

给定二叉搜索树(BST)的根节点 root 和一个整数值 val

你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 null 。

示例 1:

输入:root = [4,2,7,1,3], val = 2
输出:[2,1,3]

示例 2:

输入:root = [4,2,7,1,3], val = 5
输出:[]

解答代码:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */


 // 递归
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (root == NULL || root->val == val) return root;

        TreeNode* result;

        if (root->val > val) result = searchBST(root->left, val);
        if (root->val < val) result = searchBST(root->right, val);

        return result;
    }
};

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

4.力扣98:验证二叉搜索树:

题目描述:

给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下:

  • 节点的左

    子树

    只包含 小于 当前节点的数。
  • 节点的右子树只包含 大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

输入:root = [2,1,3]
输出:true

示例 2:

输入:root = [5,1,4,null,null,3,6]
输出:false
解释:根节点的值是 5 ,但是右子节点的值是 4 。

解答代码1:

思路:利用前序遍历将二叉树中的数据放入一个数组中,判断数组中的元素是否从小到大排列,同时要注意二叉搜索树中不能有相同的元素(故判断条件为小于等于)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> vec;
    void traversal(TreeNode* root) {
        if (root == NULL) return;

        if (root->left) traversal(root->left);
        vec.push_back(root->val);
        if (root->right) traversal(root->right);

    }

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

解答代码2(利用前序遍历和双指针):

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
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;
    }
};

标签:right,TreeNode,val,随想录,Day17,打卡,root,节点,left
From: https://blog.csdn.net/jianbaigreat/article/details/143469226

相关文章

  • 代码随想录打卡Day16
    1.力扣531:找树左下角的值。题目描述:给定一个二叉树的 根节点 root,请找出该二叉树的 最底层 最左边 节点的值。假设二叉树中至少有一个节点。示例1:输入:root=[2,1,3]输出:1示例2:输入:[1,2,3,4,null,5,6,null,null,7]输出:7解答代码:/***Defi......
  • 代码随想录算法训练营第十六天|leetcode513.找树左下角的值、leetcode112.路径总和、l
    1leetcode513.找树左下角的值题目链接:513.找树左下角的值-力扣(LeetCode)文章链接:代码随想录视频链接:怎么找二叉树的左下角?递归中又带回溯了,怎么办?|LeetCode:513.找二叉树左下角的值_哔哩哔哩_bilibili思路:就是用一个东西存储result,使用后续遍历,如果遇到了最深的那一个值,就......
  • python+flask计算机毕业设计高校学生课堂考勤打卡APP的设计和实现(程序+开题+论文)
    本系统(程序+源码+数据库+调试部署+开发环境)带论文文档1万字以上,文末可获取,系统界面在最后面。系统程序文件列表开题报告内容一、选题背景关于高校学生课堂考勤的研究,现有研究多集中在传统点名方式的改进以及基于单一技术的考勤系统开发。例如,有的研究专注于利用蓝牙技术实......
  • python+flask计算机毕业设计好骑行打卡园app系统(程序+开题+论文)
    本系统(程序+源码+数据库+调试部署+开发环境)带论文文档1万字以上,文末可获取,系统界面在最后面。系统程序文件列表开题报告内容好骑行打卡园app系统毕业设计相关内容一、选题背景关于骑行打卡类APP的研究,现有研究主要以骑行记录和路线规划为主,专门针对骑行打卡园这种集打卡......
  • 代码随想录算法训练营第十四天|leetcode226. 翻转二叉树、leetcode101.对称二叉树、le
    1leetcode226.翻转二叉树题目链接:226.翻转二叉树-力扣(LeetCode)文章链接:代码随想录视频链接:听说一位巨佬面Google被拒了,因为没写出翻转二叉树|LeetCode:226.翻转二叉树哔哩哔哩bilibili自己的思路:之前想过就是使用层序遍历的方法来做这一道题目,后来感觉有一些行不通,就......
  • 代码随想录算法训练营第十三天|二叉树的理论基础、二叉树的递归遍历、二叉树的层序遍
    1二叉树的理论基础文章链接:代码随想录视频链接:关于二叉树,你该了解这些!|二叉树理论基础一网打尽,二叉树的种类、二叉树的存储方式、二叉树节点定义、二叉树的遍历顺序哔哩哔哩bilibili1.1二叉树的种类满二叉树所有节点处的值都排满了,没有空的完全二叉树只有在最后......
  • 代码随想录之哈希表刷题总结
    1.哈希表理论基础哈希表-(hashtable),数组其实就是一张哈希表,哈希表中关键码就是数组的索引下标,然后通过下标直接访问数组中的元素。如下图:1.1哈希函数把学生的姓名直接映射为哈希表上的索引,然后就可以通过查询索引下标快速知道这位同学是否在这所学校里了。哈希函数如下图......
  • 考研打卡(9)
    开局(9)开始时间 2024-11-0513:57:18结束时间 2024-11-05 14:26:41今天要去打剧本杀数据结构将一个n*n的对称矩阵A的下三角按行存放在一堆数组B中,A[0][0]存放在B[0][0]中,那么第i行的对角元素A[i][i]在B中的存放位置是____(湖南大学2012)A(i+3)*i/2B(i+1)*i/2C(2......
  • 代码随想录刷题学习日记
    仅为个人记录复盘学习历程,解题思路来自代码随想录代码随想录刷题笔记总结网址:代码随想录559.n叉树的最大深度(层序遍历法)给定一个n叉树,找到其最大深度。最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。提供参数:根结点root关键思路:和二叉树的层序遍历找最......