第 28 題：對稱的二叉樹
傳送門：對稱的二叉樹，藕枧酰客網(wǎng) online judge 地址。
請實(shí)現(xiàn)一個(gè)函數(shù)疙渣，用來判斷一棵二叉樹是不是對稱的。
如果一棵二叉樹和它的鏡像一樣堆巧，那么它是對稱的妄荔。
樣例：
如下圖所示二叉樹
[1,2,2,3,4,4,3,null,null,null,null,null,null,null,null]為對稱二叉樹：1 / \ 2 2 / \ / \ 3 4 4 3如下圖所示二叉樹
[1,2,2,null,4,4,3,null,null,null,null,null,null]不是對稱二叉樹：1 / \ 2 2 \ / \ 4 4 3
分析：LeetCode 上有類似的問題泼菌，使用雙端隊(duì)列可以完成，畫圖畫到第 4 層就非常清晰了啦租。
同 LeetCode 第 101 題哗伯。
解法1：遞歸寫法。
Java 代碼：
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public class Solution {
boolean isSymmetrical(TreeNode pRoot) {
if (pRoot == null) {
return true;
}
return helper(pRoot.left, pRoot.right);
}
private boolean helper(TreeNode pRoot1, TreeNode pRoot2) {
if (pRoot1 == null && pRoot2 == null) {
return true;
}
if (pRoot1 == null || pRoot2 == null || pRoot1.val != pRoot2.val) {
return false;
}
return helper(pRoot1.left, pRoot2.right) && helper(pRoot1.right, pRoot2.left);
}
}
Python 代碼：
# Definition for a binary tree node.
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
# 遞歸寫法：得引入輔助函數(shù)
class Solution(object):
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
# 先寫遞歸終止條件
if root is None:
return True
return self.__helper(root.left, root.right)
def __helper(self, p1, p2):
if p1 is None and p2 is None:
return True
if p1 is None or p2 is None:
return False
return p1.val == p2.val and self.__helper(p1.left, p2.right) and self.__helper(p1.right, p2.left)
解法2：非遞歸寫法篷角，借助雙端隊(duì)列輔助判斷焊刹。自己畫一個(gè)圖，就好理解了恳蹲。
Python 代碼：
# Definition for a binary tree node.
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
# 非遞歸寫法：借助雙端隊(duì)列輔助判斷
class Solution(object):
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
# 先寫遞歸終止條件
if root is None:
return True
# 其實(shí)應(yīng)該用 from collections import deque
deque = []
deque.insert(0, root.left)
deque.append(root.right)
while deque:
l_node = deque.pop(0)
r_node = deque.pop()
# 這一步一定不要忘記了
if l_node is None and r_node is None:
continue
if l_node is None or r_node is None:
return False
# 代碼走到這里一定有 l_node 和 r_node 非空
# 因此可以取出 val 進(jìn)行判斷了
if l_node.val != r_node.val:
return False
deque.insert(0, l_node.right)
deque.insert(0, l_node.left)
deque.append(r_node.left)
deque.append(r_node.right)
return True
“大雪菜”的寫法：用棧模擬遞歸虐块，對根結(jié)點(diǎn)的左子樹，我們用中序遍歷嘉蕾；對根結(jié)點(diǎn)的右子樹贺奠，我們用反中序遍歷。
則兩個(gè)子樹互為鏡像错忱，當(dāng)且僅當(dāng)同時(shí)遍歷兩棵子樹時(shí)儡率，對應(yīng)結(jié)點(diǎn)的值相等。
時(shí)間復(fù)雜度：樹中每個(gè)結(jié)點(diǎn)僅被遍歷一遍以清，所以時(shí)間復(fù)雜度是 儿普。
C++ 代碼：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if (!root) return true;
stack<TreeNode*> left, right;
TreeNode *lc = root->left;
TreeNode *rc = root->right;
while(lc || rc || left.size())
{
while (lc && rc)
{
left.push(lc), right.push(rc);
lc = lc->left, rc = rc->right;
}
if (lc || rc) return false;
lc = left.top(), rc = right.top();
left.pop(), right.pop();
if (lc->val != rc->val) return false;
// 這里反過來操作
lc = lc->right, rc = rc->left;
}
return true;
}
};
作者：yxc
鏈接：https://www.acwing.com/solution/AcWing/content/747/
來源：AcWing
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)掷倔，非商業(yè)轉(zhuǎn)載請注明出處眉孩。
