题目描述:
给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
举例:
示例: 给定二叉树 [3,9,20,null,null,15,7] ,
3
/ 9 20
/ 15 7
返回它的最大深度 3 。
学习心得(自己琢磨的):可以用于网页链接的最大延伸找查。就是看某颗“树”,
最深的根有好深。
解题思路:采用递归,左右结点权值相加比较。
实现:(C++)
class Solution { public: int maxDepth(TreeNode* root) { if( root==NULL ) return 0; int l=0,r=0; l+=maxDepth( root->left )+1; //采用递归,提醒一下,每次递归返回后,“root”是上一层的“root” r+=maxDepth( root->right )+1; return l>r?l:r ; } };
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
树_第2题:验证二叉搜索树
题目描述:
给定一个二叉树,判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征:
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
举例:
示例 1:
输入:
2
/ 1 3
输出: true
示例 2:
输入:
5
/ 1 4
/ 3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ,但是其右子节点值为 4 。
应用背景(百度百科):二叉搜索树作为一种经典的数据结构,它既有链表的快速插入
与删除操作的特点,又有数组快速查找的优势;所以应用十分广泛,例如在文件系统和
数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。
解题思路:再建立一个函数,递归它,左子树和右子树来回递归,并返回true或false。
实现:(C++)
/** * Definition for a binary tree node. * struct TreeNode { * int val;
项目 |
方法 |
301Yw |
ZJGbu2643 |
31wlR |
2007.08.15 12-27-44 |
lIDuO |
抖音牛逼姐 |
Rut7L |
2007-04-27 03:24:47 |
377EJ |
dUQO64315 | * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool PD(TreeNode* root,long min,long max) //新建立的一个函数PD:判断。min:最小值(下界)。max:最大值(上界) { if( root==NULL ) return true; if( (root->val <= min)||(root->val >= max) ) return false; return PD(root->left,min,root->val)&&PD(root->right,root->val,max); //提醒一下,每次进行递归又返回值后,注意此时的“root”、"min"、"max"分别是什么 } bool isValidBST(TreeNode* root) {return PD(root,LONG_MIN,LONG_MAX);} //LONG_MIN和LONG_MAX分别是long型的最小值和最大值 };
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
树_第3题:对称二叉树
题目描述:
给定一个二叉树,检查它是否是镜像对称的。
举例
例如,二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ 2 2
/ \ / 3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/ 2 2
\ 3 3
学习心得(自己琢磨的):有点类似于判断回文链表,只不过“树”是分散的“链表”。
在这里再次提一下“对称性”。
解题思路:灵活运用递归。参考力扣论坛一位大佬的评论(递归点:我在尝试判断左树与右树对称的条件时,发现其跟两树 的孩子的对称情况有关系。
def 函数A(左树,右树): 左树节点值等于右树节点值 且 函数A(左树的左子树,右树的右子树),函数A(左树的右子树,右树的左子树)均为真 才返回真
实现完毕。。。)
实现:(C++)
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool equal( TreeNode* root1,TreeNode* root2 ) { if( root1==NULL&&root2==NULL ) return true; //左右孩子(即左右子树)都为空,则对称 if( root1==NULL&&root2!=NULL) return false; //左右孩子有一个为空,另一个不为空,则不对称 if( root1!=NULL&&root2==NULL ) return false; //左右孩子有一个为空,另一个不为空,则不对称 if( root1->val!=root2->val ) return false; //左右孩子的值不一样,则不对称 return equal(root1->left,root2->right)&&equal(root1->right,root2->left); //递归,注意左右孩子的位置 } bool isSymmetric(TreeNode* root) { if(root==NULL) return true; return equal( root->left,root->right ); } };
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
搜索和排序_第1题: 合并两个有序数组
题目描述:
给你两个有序整数数组 nums1 和 nums2,请你将 nums2 合并到 nums1 中,使 nums1 成为一个有序数组。
举例:
示例:
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
说明:
- 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
- 你可以假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。
学习心得(自己琢磨的):怎么说呢,和前面“链表”的题中的“合并两个有序链表”有相像之处,
但这里用的是vector容器,用的下标来“指示”每个结点。
解题思路:用“双坐标”来解决,有点类似于在解决“合并两个有序链表”时用的“双指针”。 这里也还需要另外建立一个“坐标指示”,用于从尾到头地指示一遍nums1的所有坐标。
实现:(C++)
class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { int i=nums1.size()-1; m--; n--; while( i!=m ) //终止条件 { if( m>=0&&nums1[m] > nums2[n] ) //m>=0不能舍去哦,不然会越界 swap( nums1[m--],nums1[i--] ); //①新学到vector里的一个新函数swap( 数据值,数据值 ),作用:交换相应的两个数据的值 else swap( nums2[n--],nums1[i--] ); } } };
|