Tree2

发表于 更新于 分类于 ，

题目描述[原题链接][https://leetcode-cn.com/problems/symmetric-tree/]

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

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

算法描述

​ 要检测二叉树是否是镜像，从根节点开始左右同时遍历，分两对；首先，左子树向左节点遍历与右子树与右节点遍历，这是第一对，第二对，左子树向右节点遍历，右子树向左节点遍历，过程中判断每个节点的val是否相等，不相等直接返回false、相等就继续向下遍历，直到走完整个树

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool judge(TreeNode* t1,TreeNode* t2){
        if(t1==NULL&&t2==NULL)return true;
        if((t1==NULL&&t2!=NULL)||(t2==NULL&&t1!=NULL))return false;
        if(t1->val==t2->val)return judge(t1->right,t2->left)&&judge(t1->left,t2->right);
        return false;
    }
    
    bool isSymmetric(TreeNode* root) {
        if(!root){
            return true;
        }
        return judge(root->left,root->right);
    }
};

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    
    public boolean judge(TreeNode l,TreeNode r){
        if(l==null&&r==null)return true;
        if((l==null&&r!=null)||(l!=null&&r==null))return false;
        if(l.val==r.val)return judge(l.left,r.right)&&judge(l.right,r.left);
        return false;
    }
    
    public boolean isSymmetric(TreeNode root) {
        if(root==null)return true;
        return judge(root.left,root.right);
    }
}