剑指offer——28. 对称的二叉树

28. 对称的二叉树

NowCoder

题目描述

解题思路

/**
思路1：递归
-镜像
--1 根节点相同 
--2 左右子树镜像
    根的左子节点=根的右子节点
*/

/**
 * 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) {
        //边界
        if(!root) return true; //空树对称
        return Symmetric(root->left, root->right);
    }
    
    //判断左右是否镜像
    bool Symmetric(TreeNode* left,TreeNode* right)
    {
        //边界条件 找到最后了 判断如果时left和right均为空 则匹配完成
        if(!left || !right) return !left && !right;
        //判断规则  值相同 递归 左子树的左==右子树的右 和 左子树的右==右子树的左 镜像
        return left->val == right->val && Symmetric(left->left, right->right) &&  Symmetric(left->right, right->left);
        // if(left->val == right->val)
        // {
        //     return Symmetric(left->left, right->right) &&  Symmetric(left->right, right->left);
        // }
        // else return false;
    }
};