树的刷题,嗝

今天忘记带本子了,就没有学习java了,于是一心刷题,好烦遇到了两个奇怪的题目,我没跟题解写的,但是我是没想到奇怪的样例.

no.1

617. 合并二叉树

难度简单1221收藏分享切换为英文接收动态反馈

给你两棵二叉树： 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]

提示：

• 两棵树中的节点数目在范围 [0, 2000] 内
• -104 <= Node.val <= 104

我本来也不太会,想着如何把子节点变换,直到看到了题解里面,函数的返回值是节点指针,于是我悟了

一下就会应用了

struct TreeNode* mergeTrees(struct TreeNode* root1, struct TreeNode* root2){if(root1==NULL){return root2;}if(root2==NULL){return root1;}
struct TreeNode* root3= (struct TreeNode*)malloc(sizeof(struct TreeNode));root3->val=root1->val+root2->val;root3->left=mergeTrees(root1->left,root2->left);root3->right=mergeTrees(root1->right,root2->right);return root3;
}

左节点空的的,返回右节点

反之 

要是都不为空就定义节点等于root1+root2,从根节点开始

遍历下去,最后root3就是新的合并树的头节点

no.2

剑指 Offer II 047. 二叉树剪枝

难度中等71收藏分享切换为英文接收动态反馈

给定一个二叉树 根节点 root ，树的每个节点的值要么是 0，要么是 1。请剪除该二叉树中所有节点的值为 0 的子树。

节点 node 的子树为 node 本身，以及所有 node 的后代。

示例 1:

输入: [1,null,0,0,1]
输出: [1,null,0,null,1] 
解释: 
只有红色节点满足条件“所有不包含 1 的子树”。
右图为返回的答案。

示例 2:

输入: [1,0,1,0,0,0,1]
输出: [1,null,1,null,1]
解释: 

示例 3:

输入: [1,1,0,1,1,0,1,0]
输出: [1,1,0,1,1,null,1]
解释: 

提示:

• 二叉树的节点个数的范围是 [1,200]
• 二叉树节点的值只会是 0 或 1

依旧以节点指针返回

对节点的left,以及right遍历判断,要是不是0就返回原来的指针

要是0就返回NULL

这个思想就是好

struct TreeNode* pruneTree(struct TreeNode* root){if(root==NULL){//空的返回return NULL;}root->left=pruneTree(root->left);//往下查root->right=pruneTree(root->right);//往下查
if(root->left==NULL&&root->right==NULL&&root->val==0){//发现是0且是根节点,直接变成nullreturn NULL;}return root;
}

可以删除的点就是为根节点,且值等于0,而且下面的节点先删了,上面的到就是根节点了,也是向下搜索

代码短就是爽,理解到位直接干废

no.3

力扣嘉年华上的 DIY 手工展位准备了一棵缩小版的 二叉 装饰树 root 和灯饰，你需要将灯饰逐一插入装饰树中，要求如下：

完成装饰的二叉树根结点与 root 的根结点值相同
若一个节点拥有父节点，则在该节点和他的父节点之间插入一个灯饰（即插入一个值为 -1 的节点）。具体地：
在一个 父节点 x 与其左子节点 y 之间添加 -1 节点， 节点 -1、节点 y 为各自父节点的左子节点，
在一个 父节点 x 与其右子节点 y 之间添加 -1 节点， 节点 -1、节点 y 为各自父节点的右子节点，
现给定二叉树的根节点 root ，请返回完成装饰后的树的根节点。
示例 1：

输入：
root = [7,5,6]

输出：[7,-1,-1,5,null,null,6]

解释：如下图所示，

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/KnLfVT
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

和上面的差不多的,判断是否要插入装饰,左节点不空就插入,右节点不空就插入一个

让当前节点的儿子等于新建的节点,新建的节点调用,自己使得下面的节点指向新建的装饰

struct TreeNode* expandBinaryTree(struct TreeNode* root){if(root==NULL){return NULL;}if(root->right==NULL&&root->left==NULL){return root;}struct TreeNode* roots1=(struct TreeNode*)malloc(sizeof(struct TreeNode));struct TreeNode* roots2=(struct TreeNode*)malloc(sizeof(struct TreeNode));if(root->left!=NULL){roots1->val=-1;roots1->left=expandBinaryTree(root->left);roots1->right=NULL;}if(root->right!=NULL){roots2->val=-1; roots2->left=NULL;roots2->right=expandBinaryTree(root->right);}if(root->left!=NULL){root->left=roots1;}if(root->right!=NULL){root->right=roots2;}return root;

但是千千万万注意逻辑顺寻 ,不要搞错了,有课逻辑就完全的ok了

no.4

剑指 Offer 55 - II. 平衡二叉树

难度简单354收藏分享切换为英文接收动态反馈

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

    3/ \9  20/  \15   7

返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

       1/ \2   2/ \3   3/ \4   4

返回 false 。

限制：

• 0 <= 树的结点个数 <= 10000

看了一会想想了想,才相信确实是求高度,和昨天的好像是一毛一样的呀,我试着我把代码,拿来搞了一下额,直接过了

bool isBalanced(struct TreeNode* root){int l=1;dfs(root,&l);if(l==1)return true;elsereturn false;
}
int max(int a,int b){if(a>b)return a;elsereturn b;}int dfs(struct TreeNode* root,int* l){if(root==NULL){return 0;}int ll=dfs(root->left,l)+1;int r=dfs(root->right,l)+1;if(abs(ll-r)>1){*l=0;}return max(ll,r);}

还来一句求高度,你会了吗?简单的递归思想 

no.5

剑指 Offer 26. 树的子结构

难度中等741收藏分享切换为英文接收动态反馈

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

例如:
给定的树 A:

     3
    / \
   4   5
  / \
 1   2
给定的树 B：

   4 
  /
 1
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 1：

输入：A = [1,2,3], B = [3,1]
输出：false

示例 2：

输入：A = [3,4,5,1,2], B = [4,1]
输出：true

限制：

0 <= 节点个数 <= 10000

我的思想是,找了一点与节点的值相同就往下查,动态的遍历,左和右边的遍历都是对的就可以修改false,但是没有过,报错的样例,我自己运行了答案是对的

无语了

bool b=false;bool dfs(struct TreeNode* A, struct TreeNode* B){if(B==NULL){return true;}if(A==NULL){return false;}if(B->val==A->val&&b==false){bool r=dfs(A->right,B->right);bool l=dfs(A->left,B->left);if(r==true&&l==true){b=true;return true;}else{b=false;return false;}}if(A->left!=NULL)dfs(A->left,B);if(A->right!=NULL)dfs(A->right,B);return false;
}bool isSubStructure(struct TreeNode* A, struct TreeNode* B){dfs(A,B);
if(B==NULL){return false;
}return b; }

搜索到底向上返回bool,一直是true答案就会是true,但是遍历得到了0,那就往上返回的就是0

就算变成了true也会变成false,而且是找的了相等才会往下遍历 ,而且要是查到B为NULL那就是true 我觉得完全是对的,可以样例不让过,还给的神奇的样例.

ok今天完结哈哈!