營(yíng)銷(xiāo)網(wǎng)站建設(shè)解決方案中國(guó)營(yíng)銷(xiāo)網(wǎng)
今天忘記帶本子了,就沒(méi)有學(xué)習(xí)java了,于是一心刷題,好煩遇到了兩個(gè)奇怪的題目,我沒(méi)跟題解寫(xiě)的,但是我是沒(méi)想到奇怪的樣例.
no.1
617. 合并二叉樹(shù)
難度簡(jiǎn)單1221收藏分享切換為英文接收動(dòng)態(tài)反饋
給你兩棵二叉樹(shù)：?root1?和?root2?。
想象一下，當(dāng)你將其中一棵覆蓋到另一棵之上時(shí)，兩棵樹(shù)上的一些節(jié)點(diǎn)將會(huì)重疊（而另一些不會(huì)）。你需要將這兩棵樹(shù)合并成一棵新二叉樹(shù)。合并的規(guī)則是：如果兩個(gè)節(jié)點(diǎn)重疊，那么將這兩個(gè)節(jié)點(diǎn)的值相加作為合并后節(jié)點(diǎn)的新值；否則，不為?null 的節(jié)點(diǎn)將直接作為新二叉樹(shù)的節(jié)點(diǎn)。
返回合并后的二叉樹(shù)。
注意:?合并過(guò)程必須從兩個(gè)樹(shù)的根節(jié)點(diǎn)開(kāi)始。
示例 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]
提示：
- 兩棵樹(shù)中的節(jié)點(diǎn)數(shù)目在范圍?
[0, 2000]?內(nèi) -104?<= Node.val <= 104
我本來(lái)也不太會(huì),想著如何把子節(jié)點(diǎn)變換,直到看到了題解里面,函數(shù)的返回值是節(jié)點(diǎn)指針,于是我悟了
一下就會(huì)應(yīng)用了
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;
}左節(jié)點(diǎn)空的的,返回右節(jié)點(diǎn)
反之?
要是都不為空就定義節(jié)點(diǎn)等于root1+root2,從根節(jié)點(diǎn)開(kāi)始
遍歷下去,最后root3就是新的合并樹(shù)的頭節(jié)點(diǎn)
no.2
劍指 Offer II 047. 二叉樹(shù)剪枝
難度中等71收藏分享切換為英文接收動(dòng)態(tài)反饋
給定一個(gè)二叉樹(shù)?根節(jié)點(diǎn)?root?，樹(shù)的每個(gè)節(jié)點(diǎn)的值要么是?0，要么是?1。請(qǐng)剪除該二叉樹(shù)中所有節(jié)點(diǎn)的值為?0?的子樹(shù)。
節(jié)點(diǎn)?node?的子樹(shù)為?node?本身，以及所有?node?的后代。
示例 1:
輸入: [1,null,0,0,1] 輸出: [1,null,0,null,1] 解釋: 只有紅色節(jié)點(diǎn)滿(mǎn)足條件“所有不包含 1 的子樹(shù)”。 右圖為返回的答案。
示例 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] 解釋:
提示:
- 二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)的范圍是?
[1,200] - 二叉樹(shù)節(jié)點(diǎn)的值只會(huì)是?
0?或?1
依舊以節(jié)點(diǎn)指針?lè)祷?/strong>
對(duì)節(jié)點(diǎn)的left,以及right遍歷判斷,要是不是0就返回原來(lái)的指針
要是0就返回NULL
這個(gè)思想就是好
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){//發(fā)現(xiàn)是0且是根節(jié)點(diǎn),直接變成nullreturn NULL;}return root;
}可以刪除的點(diǎn)就是為根節(jié)點(diǎn),且值等于0,而且下面的節(jié)點(diǎn)先刪了,上面的到就是根節(jié)點(diǎn)了,也是向下搜索
代碼短就是爽,理解到位直接干廢
no.3
力扣嘉年華上的 DIY 手工展位準(zhǔn)備了一棵縮小版的 二叉 裝飾樹(shù) root 和燈飾，你需要將燈飾逐一插入裝飾樹(shù)中，要求如下：
完成裝飾的二叉樹(shù)根結(jié)點(diǎn)與 root 的根結(jié)點(diǎn)值相同
若一個(gè)節(jié)點(diǎn)擁有父節(jié)點(diǎn)，則在該節(jié)點(diǎn)和他的父節(jié)點(diǎn)之間插入一個(gè)燈飾（即插入一個(gè)值為 -1 的節(jié)點(diǎn)）。具體地：
在一個(gè) 父節(jié)點(diǎn) x 與其左子節(jié)點(diǎn) y 之間添加 -1 節(jié)點(diǎn)， 節(jié)點(diǎn) -1、節(jié)點(diǎn) y 為各自父節(jié)點(diǎn)的左子節(jié)點(diǎn)，
在一個(gè) 父節(jié)點(diǎn) x 與其右子節(jié)點(diǎn) y 之間添加 -1 節(jié)點(diǎn)， 節(jié)點(diǎn) -1、節(jié)點(diǎn) y 為各自父節(jié)點(diǎn)的右子節(jié)點(diǎn)，
現(xiàn)給定二叉樹(shù)的根節(jié)點(diǎn) root ，請(qǐng)返回完成裝飾后的樹(shù)的根節(jié)點(diǎn)。
示例 1：
輸入：
root = [7,5,6]
輸出：[7,-1,-1,5,null,null,6]
解釋：如下圖所示，
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/KnLfVT
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
和上面的差不多的,判斷是否要插入裝飾,左節(jié)點(diǎn)不空就插入,右節(jié)點(diǎn)不空就插入一個(gè)
讓當(dāng)前節(jié)點(diǎn)的兒子等于新建的節(jié)點(diǎn),新建的節(jié)點(diǎn)調(diào)用,自己使得下面的節(jié)點(diǎn)指向新建的裝飾
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;
但是千千萬(wàn)萬(wàn)注意邏輯順尋 ,不要搞錯(cuò)了,有課邏輯就完全的ok了
no.4
劍指 Offer 55 - II. 平衡二叉樹(shù)
難度簡(jiǎn)單354收藏分享切換為英文接收動(dòng)態(tài)反饋
輸入一棵二叉樹(shù)的根節(jié)點(diǎn)，判斷該樹(shù)是不是平衡二叉樹(shù)。如果某二叉樹(shù)中任意節(jié)點(diǎn)的左右子樹(shù)的深度相差不超過(guò)1，那么它就是一棵平衡二叉樹(shù)。
示例 1:
給定二叉樹(shù)?[3,9,20,null,null,15,7]
3/ \9 20/ \15 7
返回?true?。
示例 2:
給定二叉樹(shù)?[1,2,2,3,3,null,null,4,4]
1/ \2 2/ \3 3/ \4 4
返回?false?。
限制：
0 <= 樹(shù)的結(jié)點(diǎn)個(gè)數(shù) <= 10000
看了一會(huì)想想了想,才相信確實(shí)是求高度,和昨天的好像是一毛一樣的呀,我試著我把代碼,拿來(lái)搞了一下額,直接過(guò)了
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);}還來(lái)一句求高度,你會(huì)了嗎?簡(jiǎn)單的遞歸思想?
no.5
劍指 Offer 26. 樹(shù)的子結(jié)構(gòu)
難度中等741收藏分享切換為英文接收動(dòng)態(tài)反饋
輸入兩棵二叉樹(shù)A和B，判斷B是不是A的子結(jié)構(gòu)。(約定空樹(shù)不是任意一個(gè)樹(shù)的子結(jié)構(gòu))
B是A的子結(jié)構(gòu)， 即 A中有出現(xiàn)和B相同的結(jié)構(gòu)和節(jié)點(diǎn)值。
例如:
給定的樹(shù) A:
? ? ?3
? ? / \
? ?4 ? 5
? / \
?1 ? 2
給定的樹(shù) B：
? ?4?
? /
?1
返回 true，因?yàn)?B 與 A 的一個(gè)子樹(shù)擁有相同的結(jié)構(gòu)和節(jié)點(diǎn)值。
示例 1：
輸入：A = [1,2,3], B = [3,1] 輸出：false
示例 2：
輸入：A = [3,4,5,1,2], B = [4,1] 輸出：true
限制：
0 <= 節(jié)點(diǎn)個(gè)數(shù) <= 10000
我的思想是,找了一點(diǎn)與節(jié)點(diǎn)的值相同就往下查,動(dòng)態(tài)的遍歷,左和右邊的遍歷都是對(duì)的就可以修改false,但是沒(méi)有過(guò),報(bào)錯(cuò)的樣例,我自己運(yùn)行了答案是對(duì)的
無(wú)語(yǔ)了
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答案就會(huì)是true,但是遍歷得到了0,那就往上返回的就是0
就算變成了true也會(huì)變成false,而且是找的了相等才會(huì)往下遍歷 ,而且要是查到B為NULL那就是true 我覺(jué)得完全是對(duì)的,可以樣例不讓過(guò),還給的神奇的樣例.
ok今天完結(jié)哈哈!