乍一看无从下手，但用递归其实很好解决。 根据题目的描述，镜像对称，就是左右两边相等，也就是左子树和右子树是相当的。 注意这句话，左子树和右子相等，也就是说要递归的比较左子树和右子树。 我们将根节点的左子树记做 left，右子树记做 right。比较 left 是否等于 right，不等的话直接返回就可以了。 如果相当，比较 left 的左节点和 right 的右节点，再比较 left 的右节点和 right 的左节点 比如看下面这两个子树 (他们分别是根节点的左子树和右子树)，能观察到这么一个规律： 左子树 2 的左孩子 右子树 2 的右孩子 左子树 2 的右孩子 右子树 2 的左孩子
2 2
/ \ / \
3 4 4 3
/ \ / \ / \ / \
8 7 6 5 5 6 7 8
根据上面信息可以总结出递归函数的两个条件： 终止条件：
Left 和 right 不等，或者 left 和 right 都为空 递归的比较 left，left 和 right. Right，递归比较 left，right 和 right. Left 动态图如下：
https://pic.leetcode-cn.com/2449af8862537df2cbbc45a07764415c1a10769677c822fa271ea7447c8fa128-2.gif
算法的时间复杂度是 O (n) ，因为要遍历 n 个节点
空间复杂度是 O (n)，空间复杂度是递归的深度，也就是跟树高度有关，最坏情况下树变成一个链表结构，高度是 n。
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root==null) {
return true;
}
//调用递归函数，比较左节点，右节点
return dfs(root.left,root.right);
}
boolean dfs(TreeNode left, TreeNode right) {
//递归的终止条件是两个节点都为空
//或者两个节点中有一个为空
//或者两个节点的值不相等
if(left==null && right==null) {
return true;
}
if(left==null || right==null) {
return false;
}
if(left.val!=right.val) {
return false;
}
//再递归的比较 左节点的左孩子 和 右节点的右孩子
//以及比较 左节点的右孩子 和 右节点的左孩子
return dfs(left.left,right.right) && dfs(left.right,right.left);
}
}
栈实现
public boolean isSymmetrical (TreeNode pRoot) {
// write code here
//层序遍历解决+队列
if(pRoot==null){
return true;
}
if(pRoot == null) return true;
Stack<TreeNode> s = new Stack<>();
s.push(pRoot.left);
s.push(pRoot.right);
while(!s.empty()) {
TreeNode right = s.pop();//成对取出
TreeNode left = s.pop();
if(left == null && right == null) continue;
if(left == null || right == null) return false;
if(left.val != right.val) return false;
//成对插入
s.push(left.left);
s.push(right.right);
s.push(left.right);
s.push(right.left);
}
return true;
}