題目
思路
找到遞歸點(diǎn)：左樹與右樹對(duì)稱與否，與其跟兩樹的子樹的對(duì)稱情況有關(guān)系。
遞歸結(jié)束條件：
- 都為空指針則返回 true
- 只有一個(gè)為空則返回 false
- 兩個(gè)指針當(dāng)前節(jié)點(diǎn)值不相等 返回false
遞歸過程：
- 判斷 A 的右子樹與 B 的左子樹是否對(duì)稱
- 判斷 A 的左子樹與 B 的右子樹是否對(duì)稱
圖解思路
代碼實(shí)現(xiàn)
C++
class Solution {
public:
bool compare(TreeNode* left, TreeNode* right) {
// 首先排除空節(jié)點(diǎn)的情況
if (left == NULL && right != NULL) return false;
else if (left != NULL && right == NULL) return false;
else if (left == NULL && right == NULL) return true;
// 排除了空節(jié)點(diǎn)，再排除數(shù)值不相同的情況
else if (left->val != right->val) return false;
// 此時(shí)就是：左右節(jié)點(diǎn)都不為空，且數(shù)值相同的情況
// 此時(shí)才做遞歸，做下一層的判斷
bool outside = compare(left->left, right->right); // 左子樹：左、 右子樹：右
bool inside = compare(left->right, right->left); // 左子樹：右、 右子樹：左
bool isSame = outside && inside; // 左子樹：中、 右子樹：中 （邏輯處理）
return isSame;
}
bool isSymmetric(TreeNode* root) {
if (root == NULL) return true;
return compare(root->left, root->right);
}
};
Java
public boolean isSymmetric(TreeNode root) {
if (root == null)
return true;
//從兩個(gè)子節(jié)點(diǎn)開始判斷
return isSymmetricHelper(root.left, root.right);
}
public boolean isSymmetricHelper(TreeNode left, TreeNode right) {
//如果左右子節(jié)點(diǎn)都為空，說明當(dāng)前節(jié)點(diǎn)是葉子節(jié)點(diǎn)，返回true
if (left == null && right == null)
return true;
//如果當(dāng)前節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)或者有兩個(gè)子節(jié)點(diǎn)，但兩個(gè)子節(jié)點(diǎn)的值不相同，直接返回false
if (left == null || right == null || left.val != right.val)
return false;
//然后左子節(jié)點(diǎn)的左子節(jié)點(diǎn)和右子節(jié)點(diǎn)的右子節(jié)點(diǎn)比較，左子節(jié)點(diǎn)的右子節(jié)點(diǎn)和右子節(jié)點(diǎn)的左子節(jié)點(diǎn)比較
return isSymmetricHelper(left.left, right.right) && isSymmetricHelper(left.right, right.left);
}
Python
class Solution(object):
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if not root:
return True
def dfs(left,right):
# 遞歸的終止條件是兩個(gè)節(jié)點(diǎn)都為空
# 或者兩個(gè)節(jié)點(diǎn)中有一個(gè)為空
# 或者兩個(gè)節(jié)點(diǎn)的值不相等
if not (left or right):
return True
if not (left and right):
return False
if left.val!=right.val:
return False
return dfs(left.left,right.right) and dfs(left.right,right.left)
# 用遞歸函數(shù)，比較左節(jié)點(diǎn)，右節(jié)點(diǎn)
return dfs(root.left,root.right)
Js
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isSame = function(root1,root2){
let r1,r2;
if(root1==null || root2==null)
{
if(root1==null && root2==null)
return true;
else
return false;
}
if(root1.val!==root2.val)
return false;
r1 = isSame(root1.left,root2.right);
r2 = isSame(root1.right,root2.left);
return r1 & r2;
}
var isSymmetric = function(root) {
if(root == null)
return true;
//判斷根左子樹是否和根右子樹對(duì)稱 遞歸的那l.left和r.right 以及 l.right 和r.left比較
return isSame(root.left,root.right);
};
迭代法
這道題目我們也可以使用迭代法，但要注意，這里的迭代法可不是前中后序的迭代寫法，因?yàn)楸绢}的本質(zhì)是判斷兩個(gè)樹是否是相互翻轉(zhuǎn)的，其實(shí)已經(jīng)不是所謂二叉樹遍歷的前中后序的關(guān)系了。
這里我們可以使用隊(duì)列來比較兩個(gè)樹（根節(jié)點(diǎn)的左右子樹）是否相互翻轉(zhuǎn)，（注意這不是層序遍歷）
使用隊(duì)列
通過隊(duì)列來判斷根節(jié)點(diǎn)的左子樹和右子樹的內(nèi)側(cè)和外側(cè)是否相等，如動(dòng)畫所示：
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if (root == NULL) return true;
queue<TreeNode*> que;
que.push(root->left); // 將左子樹頭結(jié)點(diǎn)加入隊(duì)列
que.push(root->right); // 將右子樹頭結(jié)點(diǎn)加入隊(duì)列
while (!que.empty()) { // 接下來就要判斷這這兩個(gè)樹是否相互翻轉(zhuǎn)
TreeNode* leftNode = que.front(); que.pop();
TreeNode* rightNode = que.front(); que.pop();
if (!leftNode && !rightNode) { // 左節(jié)點(diǎn)為空、右節(jié)點(diǎn)為空，此時(shí)說明是對(duì)稱的
continue;
}
// 左右一個(gè)節(jié)點(diǎn)不為空，或者都不為空但數(shù)值不相同，返回false
if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {
return false;
}
que.push(leftNode->left); // 加入左節(jié)點(diǎn)左孩子
que.push(rightNode->right); // 加入右節(jié)點(diǎn)右孩子
que.push(leftNode->right); // 加入左節(jié)點(diǎn)右孩子
que.push(rightNode->left); // 加入右節(jié)點(diǎn)左孩子
}
return true;
}
};
使用棧
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if (root == NULL) return true;
stack<TreeNode*> st; // 這里改成了棧
st.push(root->left);
st.push(root->right);
while (!st.empty()) {
TreeNode* leftNode = st.top(); st.pop();
TreeNode* rightNode = st.top(); st.pop();
if (!leftNode && !rightNode) {
continue;
}
if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {
return false;
}
st.push(leftNode->left);
st.push(rightNode->right);
st.push(leftNode->right);
st.push(rightNode->left);
}
return true;
}
};
