資訊專欄INFORMATION COLUMN
摘要：原題檢查兩棵二叉樹是否在經(jīng)過若干次扭轉(zhuǎn)后可以等價(jià)。扭轉(zhuǎn)的定義是，交換任意節(jié)點(diǎn)的左右子樹。等價(jià)的定義是，兩棵二叉樹必須為相同的結(jié)構(gòu)，并且對應(yīng)位置上的節(jié)點(diǎn)的值要相等。樣例是扭轉(zhuǎn)后可等價(jià)的二叉樹。
原題
檢查兩棵二叉樹是否在經(jīng)過若干次扭轉(zhuǎn)后可以等價(jià)。扭轉(zhuǎn)的定義是，交換任意節(jié)點(diǎn)的左右子樹。等價(jià)的定義是，兩棵二叉樹必須為相同的結(jié)構(gòu)，并且對應(yīng)位置上的節(jié)點(diǎn)的值要相等。
注意：你可以假設(shè)二叉樹中不會有重復(fù)的節(jié)點(diǎn)值。
樣例
1 1
/ /
2 3 and 3 2
/
4 4
是扭轉(zhuǎn)后可等價(jià)的二叉樹。
1 1
/ /
2 3 and 3 2
/ /
4 4
就不是扭轉(zhuǎn)后可以等價(jià)的二叉樹。
解題思路
Recursion - 遞歸求解，分治的思路。
注意，題目中說的是經(jīng)過若干次扭轉(zhuǎn)后可以等價(jià)，所以不要忘記考慮完全identical的情況，某一個節(jié)點(diǎn)的左右子樹翻轉(zhuǎn)一次對稱，反轉(zhuǎn)兩次還原。
文／Jason_Yuan（簡書作者）
原文鏈接：http://www.jianshu.com/p/0623...
public boolean isTweakedIdentical(TreeNode a, TreeNode b) {
if (a == null && b == null) {
return true;
}
if (a == null || b == null) {
return false;
}
if (a.val != b.val){
return false;
}
//divide
// boolean left = isTweakedIdentical(a.left, b.right);
// boolean right = isTweakedIdentical(a.right, b.left);
//注意，題目中說的是經(jīng)過若干次扭轉(zhuǎn)后可以等價(jià)，所以不要忘記考慮完全identical的情況，某一個節(jié)點(diǎn)的左右子樹翻轉(zhuǎn)一次對稱，反轉(zhuǎn)兩次還原。
boolean left = isTweakedIdentical(a.left, b.left) || isTweakedIdentical(a.left, b.right);
boolean right = isTweakedIdentical(a.right, b.right) || isTweakedIdentical(a.right, b.left);
//conquer
// if (left != true || right != true){
// return false;
// }
// else{
// return true;
// }
return left && right;
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/66439.html
problem Check if two binary trees are identical. Identical means the two binary trees have the same structure and every identical position has the same value. Example 1 1 / ...
摘要：遞歸法復(fù)雜度時(shí)間空間遞歸?？臻g思路如果兩個根節(jié)點(diǎn)一個為空，一個不為空，或者兩個根節(jié)點(diǎn)值不同，說明出現(xiàn)了不一樣的地方，返回假。代碼遞歸法復(fù)雜度時(shí)間空間遞歸?？臻g思路其實(shí)和寫法是一樣的，是比較兩個節(jié)點(diǎn)的兩個左邊，然后再比較兩個節(jié)點(diǎn)的兩個右邊。 Same Tree Given two binary trees, write a function to check if they are eq...
摘要：判斷兩棵樹是否是相同題目要求傳入兩棵樹的根節(jié)點(diǎn)，判斷這兩棵樹是否相同此題的核心就在于如何遍歷樹。定義樹的一種自然方式是遞歸的方式。一棵樹是一些節(jié)點(diǎn)的集合，這個集合可以是空集。這個遍歷算法可以用于場景如，計(jì)算一個節(jié)點(diǎn)的高度。 判斷兩棵樹是否是相同 題目要求：傳入兩棵樹的根節(jié)點(diǎn)，判斷這兩棵樹是否相同此題的核心就在于如何遍歷樹。一旦我們解決了這個問題，題目也就迎刃而解了。下面就來介紹一下 關(guān)...
摘要：代碼實(shí)現(xiàn)測試代碼輸出解析標(biāo)簽表達(dá)式基礎(chǔ)的表達(dá)式解析實(shí)現(xiàn)了，針對我們的標(biāo)簽表達(dá)式多個字符組成一個標(biāo)簽，以及去掉，加上的邏輯，稍作修改測試代碼輸出后綴表達(dá)式轉(zhuǎn)二叉樹分析根據(jù)后綴表達(dá)式的含義，符合表示前面兩個元素的運(yùn)算。用戶標(biāo)簽是個數(shù)組。 一、概述 標(biāo)簽是精細(xì)化運(yùn)營必不可少的工具，常見的使用場景有標(biāo)簽推送，千人千面的廣告展示等。在實(shí)際的業(yè)務(wù)中，標(biāo)簽往往是通過交并差非運(yùn)算組合在一起使用，比如：...
閱讀 2595·2023-04-25 22:09
閱讀 1115·2021-11-17 17:01
閱讀 1892·2021-09-04 16:45
閱讀 2682·2021-08-03 14:02
閱讀 871·2019-08-29 17:11
閱讀 3332·2019-08-29 12:23
閱讀 1153·2019-08-29 11:10
閱讀 3341·2019-08-26 13:48
