每日一道 LeetCode (21)：對稱二叉樹
?每天 3 分鐘，走上算法的逆襲之路。
?
前文合集
代碼倉庫
GitHub：https://github.com/meteor1993/LeetCode
Gitee：https://gitee.com/inwsy/LeetCode
題目：對稱二叉樹
題目來源：https://leetcode-cn.com/problems/symmetric-tree/
給定一個二叉樹，檢查它是否是鏡像對稱的。
例如，二叉樹?[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
進階：
你可以運用遞歸和迭代兩種方法解決這個問題嗎？
解題思路
LeetCode 題的順序蠻有意思的么，還按照數(shù)據(jù)結構來，先是數(shù)組，然后是列表，接著是鏈表，現(xiàn)在輪到的二叉樹，已經連續(xù)兩天是二叉樹了，這是怕我們一道題學不會還帶強化練習一下的么。。。
今天這道題和昨天那道題從解法上來講有點像，都是兩種方案，遞歸和迭代，看來處理二叉樹的問題，一般都會使用到這兩種手段。
至于這道題的解法，emmmmmmmmmmmmmmmm......
原諒我做題少，直接翻開了參考答案。
這道題的核心在于，如何判斷一個二叉樹是對稱二叉樹？
我看到官方解法把這個問題轉化了一下，轉化成下面這樣：
嗯，沒問題，確實是這樣的，竟然如此簡單。
可我為啥就是想不到呢？
菜就是做題少，多做點題就知道了。
解題方案一：遞歸
遞歸的思路很簡單，同步的移動兩個指針，一個向左移動，另一個向右移動，比較這兩個指針指向的元素是否相等。
public?boolean?isSymmetric(TreeNode?root)?{
????return?check(root,?root);
}
public?boolean?check(TreeNode?p,?TreeNode?q)?{
????if?(p?==?null?&&?q?==?null)?return?true;
????if?(p?==?null?||?q?==?null)?return?false;
????return?p.val?==?q.val?&&?check(p.left,?q.right)?&&?check(p.right,?q.left);
}
解題方案二：迭代
昨天的那道題，我們使用了兩個隊列，分別來存放兩個二叉樹進行比較，今天這道題一樣可以使用兩個隊列進行操作，只是需要一個隊列先放入左子樹，另一個隊列先放入右子樹。
public?boolean?check_2(TreeNode?p,?TreeNode?q)?{
????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?==?null?&&?node2?==?null)?continue;
????????if?((node1?==?null?||?node2?==?null)?||?(node1.val?!=?node2.val))?return?false;
????????queue1.offer(node1.left);
????????queue1.offer(node1.right);
????????queue2.offer(node2.right);
????????queue2.offer(node2.left);
????}
????return?true;
}
這個方案稍有不足，就是我們使用了兩個隊列，實際上在答案中給出的方案是使用一個隊列就可以完成的。
初始化時我們把根節(jié)點入隊兩次。每次提取兩個結點并比較它們的值（隊列中每兩個連續(xù)的結點應該是相等的，而且它們的子樹互為鏡像），然后將兩個結點的左右子結點按相反的順序插入隊列中。
public?boolean?check_1(TreeNode?p,?TreeNode?q)?{
????Queue?queue?=?new?LinkedList<>();
????queue.offer(p);
????queue.offer(q);
????while?(!queue.isEmpty())?{
????????p?=?queue.poll();
????????q?=?queue.poll();
????????if?(p?==?null?&&?q?==?null)?continue;
????????if?((p?==?null?||?q?==?null)?||?(p.val?!=?q.val))?return?false;
????????queue.offer(p.left);
????????queue.offer(q.right);
????????queue.offer(p.right);
????????queue.offer(q.left);
????}
????return?true;
}
這兩種方案，耗時都是一致的，時間復雜度都是 O(n) 。
