101. 对称二叉树

题目链接

https://leetcode-cn.com/problems/symmetric-tree/

题目描述

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

解题方案

思路

标签：dfs
递归结束条件：
- 都为空指针则返回true
- 只有一个为空则返回false
递归过程：
- 判断两个指针当前节点值是否相等
- 判断A的右子树与B的左子树是否对称
- 判断A的左子树与B的右子树是否对称
短路：在递归判断过程中存在短路现象，也就是做与操作时，如果前面的值返回false则后面的不再进行计算
时间复杂度：O(n)

代码

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return isMirror(root, root);
    }

    public boolean isMirror(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) return true;
        if (t1 == null || t2 == null) return false;
        return (t1.val == t2.val)
            && isMirror(t1.right, t2.left)
            && isMirror(t1.left, t2.right);
    }
}