給你一個二叉樹的根節點?root?， 檢查它是否軸對稱。

示例 1：

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

示例 2：

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

思路

對于二叉樹是否對稱，要比較的是根節點的左子樹與右子樹是不是相互翻轉的，其實我們要比較的是兩個樹（這兩個樹是根節點的左右子樹），所以在遞歸遍歷的過程中，也是要同時遍歷兩棵樹。

那么如何比較？

比較的是兩個子樹的里側和外側的元素是否相等。

那么遍歷的順序應該是什么樣的？

本題遍歷只能是“后序遍歷”，因為我們要通過遞歸函數的返回值來判斷兩個子樹的內側節點和外側節點是否相等。

正是因為要遍歷兩棵樹而且要比較內側和外側節點，所以準確的來說是一個樹的遍歷順序是左右中，一個樹的遍歷順序是右左中。

遞歸法

確定遞歸函數的參數和返回值 因為我們要比較的是根節點的兩個子樹是否是相互翻轉的，進而判斷這個樹是不是對稱樹，所以要比較的是兩個樹，參數自然也是左子樹節點和右子樹節點。

返回值自然是bool類型。

代碼如下：

bool compare(TreeNode left, TreeNode right) 確定終止條件 要比較兩個節點數值相不相同

節點為空的情況有：

左節點為空，右節點不為空，不對稱，return false 左不為空，右為空，不對稱 return false 左右都為空，對稱，返回true 此時已經排除掉了節點為空的情況，那么剩下的就是左右節點不為空：

左右都不為空，比較節點數值，不相同就return false 此時左右節點不為空，且數值也不相同的情況我們也處理了。

代碼如下：

if (left == NULL && right != NULL) return false; else if (left != NULL && right == NULL) return false; else if (left == NULL && right == NULL) return true; else if (left->val != right->val) return false; 因為我們把以上情況都排除之后，剩下的就是 左右節點都不為空，且數值相同的情況。

確定單層遞歸的邏輯 此時才進入單層遞歸的邏輯，單層遞歸的邏輯就是處理 左右節點都不為空，且數值相同的情況。

比較二叉樹外側是否對稱：傳入的是左節點的左孩子，右節點的右孩子。 比較內測是否對稱，傳入左節點的右孩子，右節點的左孩子。 如果左右都對稱就返回true ，有一側不對稱就返回false 。 代碼如下：

bool outside = compare(left.left, right.right); // 左子樹：左、 右子樹：右 bool inside = compare(left.right, right.left); // 左子樹：右、 右子樹：左 bool isSame = outside && inside; // 左子樹：中、 右子樹：中（邏輯處理） return isSame; 我們可以看出使用的遍歷方式，左子樹左右中，右子樹右左中

/*** Definition for a binary tree node.* public class TreeNode {* ? ? int val;* ? ? TreeNode left;* ? ? TreeNode right;* ? ? TreeNode() {}* ? ? TreeNode(int val) { this.val = val; }* ? ? TreeNode(int val, TreeNode left, TreeNode right) {* ? ? ? ? this.val = val;* ? ? ? ? this.left = left;* ? ? ? ? this.right = right;* ? ? }* }*/
class Solution {public boolean isSymmetric(TreeNode root) {if(root==null) return true;return compare(root.left,root.right);
?}boolean compare(TreeNode left,TreeNode right){if(left==null&&right!=null) return false;else if(right==null&&left!=null) return false;else if(left==null&&right==null) return true;else if(left.val!=right.val) return false;
?boolean outside=compare(left.left,right.right);boolean inside=compare(left.right,right.left);return outside&&inside;}
}

迭代法

可以使用棧來比較兩個樹（根節點的左右子樹）是否相互翻轉

也可以使用隊列

class Solution {public boolean isSymmetric(TreeNode root) {if(root==null) return true;Stack<TreeNode> stack=new Stack<>();stack.push(root.left);stack.push(root.right);while(!stack.isEmpty()){TreeNode right=stack.pop();TreeNode left=stack.pop();if(left==null && right==null){continue;}if(left==null ||right==null||(left.val!=right.val)){return false;}stack.push(left.right);stack.push(right.left);stack.push(left.left);stack.push(right.right);}return true;}
}