力扣_初级算法_树_1~3题_和_排序和搜索_1题

标签：int   合并   左右子树   尾到头   code   dep   操作   链表   优势   

树_第1题：二叉树的最大深度

题目描述：

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

举例：

示例：
给定二叉树 [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;
* 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 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& nums1, int m, vector& 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--] );
}
}
};

力扣_初级算法_树_1~3题_和_排序和搜索_1题

标签：int   合并   左右子树   尾到头   code   dep   操作   链表   优势   

原文地址：https://www.cnblogs.com/Wang-dou-dou/p/13282017.html