每日一道 LeetCode (20)：相同的樹
?每天 3 分鐘，走上算法的逆襲之路。
?
前文合集
代碼倉庫
GitHub：https://github.com/meteor1993/LeetCode
Gitee：https://gitee.com/inwsy/LeetCode
題目：相同的樹
題目來源：https://leetcode-cn.com/problems/same-tree/
給定兩個二叉樹，編寫一個函數(shù)來檢驗它們是否相同。
如果兩個樹在結(jié)構(gòu)上相同，并且節(jié)點具有相同的值，則認(rèn)為它們是相同的。
示例?1:
輸入:???????1?????????1
??????????/?\???????/?\
?????????2???3?????2???3
????????[1,2,3],???[1,2,3]
輸出:?true
示例 2:
輸入:??????1??????????1
??????????/???????????\
?????????2?????????????2
????????[1,2],?????[1,null,2]
輸出:?false
示例?3:
輸入:???????1?????????1
??????????/?\???????/?\
?????????2???1?????1???2
????????[1,2,1],???[1,1,2]
輸出:?false
解題思路
今天又見到新的數(shù)據(jù)結(jié)構(gòu)了，這次遇到的是樹，或者簡單的說是二叉樹。
例行慣例，第一次的見的數(shù)據(jù)結(jié)構(gòu)基本上都沒啥想法，直接看答案。
只能怨自己肚子里墨水太少，不會的太多，搞不定的只能答案走起，算法這玩意，答案背多了再遇到題也就有想法了。
先放一段樹的結(jié)構(gòu)代碼：
public?class?TreeNode?{
????public?int?val;
????public?TreeNode?left;
????public?TreeNode?right;
????public?TreeNode()?{}
????public?TreeNode(int?val)?{?this.val?=?val;?}
????public?TreeNode(int?val,?TreeNode?left,?TreeNode?right)?{
????????this.val?=?val;
????????this.left?=?left;
????????this.right?=?right;
????}
}
這段代碼很簡單，樹上的值是 int 類型，然后有一個左節(jié)點有一個右節(jié)點。
樹結(jié)構(gòu)介紹完畢，接下來梳理兩種遍歷樹的方案，或者說是常規(guī)操作。
解題的話提供兩種方案，一種是遞歸，一種是循環(huán)。
「遞歸」
首先極限值判斷，兩個二叉樹都為空肯定相等，如果一個為空另一個不為空肯定不相等。
接下來如果兩個二叉樹都不為空，那么首先判斷它們的根節(jié)點的值是否相同，若不相同則兩個二叉樹一定不同，若相同，再分別判斷兩個二叉樹的左子樹是否相同以及右子樹是否相同，然后接著遞歸這個過程。
「循環(huán)」
首先和上面一樣，先進行極限值判斷。
使用兩個隊列分別存儲兩個二叉樹的節(jié)點。初始時將兩個二叉樹的根節(jié)點分別加入兩個隊列。每次從兩個隊列各取出一個節(jié)點，進行操作：
比較兩個節(jié)點的值，如果兩個節(jié)點的值不相同則兩個二叉樹一定不同。 如果兩個節(jié)點的值相同，則判斷兩個節(jié)點的子節(jié)點是否為空，如果只有一個節(jié)點的左子節(jié)點為空，或者只有一個節(jié)點的右子節(jié)點為空，則兩個二叉樹的結(jié)構(gòu)不同，因此兩個二叉樹一定不同。 如果兩個節(jié)點的子節(jié)點的結(jié)構(gòu)相同，則將兩個節(jié)點的非空子節(jié)點分別加入兩個隊列，子節(jié)點加入隊列時需要注意順序，如果左右子節(jié)點都不為空，則先加入左子節(jié)點，后加入右子節(jié)點。
結(jié)果，如果循環(huán)結(jié)束的時候兩個隊列同時為空，那么這兩個二叉樹相同，如果有一個不為空，那肯定不相同。
代碼：
//?迭代
public?boolean?isSameTree(TreeNode?p,?TreeNode?q)?{
????if?(p?==?null?&&?q?==?null)?{
????????return?true;
????}?else?if?(p?==?null?||?q?==?null)?{
????????return?false;
????}?else?if?(p.val?!=?q.val)?{
????????return?false;
????}?else?{
????????return?isSameTree(p.left,?q.left)?&&?isSameTree(p.right,?q.right);
????}
}
//?循環(huán)
public?boolean?isSameTree_1(TreeNode?p,?TreeNode?q)?{
????if?(p?==?null?&&?q?==?null)?return?true;
????if?(p?==?null?||?q?==?null)?return?false;
????Queue?queue1?=?new?LinkedList<>();
????Queue?queue2?=?new?LinkedList<>();
????queue1.offer(p);
????queue2.offer(q);
????while?(!queue1.isEmpty()?&&?!queue2.isEmpty())?{
????????TreeNode?node1?=?queue1.poll();
????????TreeNode?node2?=?queue2.poll();
????????if?(node1.val?!=?node2.val)?return?false;
????????TreeNode?left1?=?node1.left,?right1?=?node1.right,?left2?=?node2.left,?right2?=?node2.right;
????????if?(left1?==?null?^?left2?==?null)?return?false;
????????if?(right1?==?null?^?right2?==?null)?return?false;
????????if?(left1?!=?null)?queue1.offer(left1);
????????if?(right1?!=?null)?queue1.offer(right1);
????????if?(left2?!=?null)?queue2.offer(left2);
????????if?(right2?!=?null)?queue2.offer(right2);
????}
????return?queue1.isEmpty()?&&?queue2.isEmpty();
}
結(jié)果我就不貼了，基本上答案區(qū)就這么兩種解題方式，也沒其他能玩出花來的方式。
