題目：對稱的二叉樹

請實現一個函數，用來判斷一棵二叉樹是不是對稱的。如果一棵二叉樹和它的鏡像一樣，那么它是對稱的。

例如，二叉樹?[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

示例 1：

輸入：root = [1,2,2,3,4,4,3]
輸出：true

示例 2：

輸入：root = [1,2,2,null,3,null,3]
輸出：false

---

解題：

方法一：遞歸

?T:O(n) S:O(n)

鏡像二叉樹滿足3個條件：

• 根節點相同
• 左孩子 與 右孩子 互為鏡像二叉樹
• 右孩子 與 左孩子 互為鏡像二叉樹

/*** 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 isMirror(TreeNode* t1, TreeNode* t2) {if (!t1 && !t2) return true;if (!t1 || !t2) return false;return (t1->val == t2->val) && isMirror(t1->left, t2->right) && isMirror(t1->right, t2->left);}bool isSymmetric(TreeNode* root) {return isMirror(root, root);}
};

方法二：非遞歸

T:O(n) S:O(n)
兩個指針從根節點出發，一個指針（根 左 右）的順序進行遍歷，一個指針（根 右 左）的順序進行便來遍歷。 看每個時刻指針指的是否是相同值得節點。
PS:不能先求出兩個序列， 再比較兩個序列是否相等。 先序遍歷是不能唯一確定一顆二叉樹的

/*** 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) {stack<TreeNode*> stk1, stk2;TreeNode *p1, *p2;p1 = p2 = root;while (p1 || !stk1.empty()) {while (p1) {if (!p2 || p1->val != p2->val) return false;  // 這里p1不可能為null, 所以還要檢查p2是否為空，p2是null則返回falsestk1.push(p1);stk2.push(p2);p1 = p1->left;  // p1一直往左遍歷p2 = p2->right; // p2一直往右遍歷}if (p2) return false;  // 這里p1是null, 所以檢查p2是否為空, p2不空則返回falsep1 = stk1.top(); stk1.pop();p1 = p1->right;p2 = stk2.top(); stk2.pop();p2 = p2->left;}return true; }
};

?

總結

以上是生活随笔為你收集整理的剑指offer：面试题28. 对称的二叉树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。