LKJZ28-对称二叉树

LKJZ28-对称二叉树 https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/ 分治递归解决 上来先考虑特殊情况root==nullptr,return true; 在子函数compare里递归解决 递归终止条件 1.左右子树都为空return true; 2.左右子树其中一个为空return false; 3.左右子树都不为空且值不相等return false; 现在只剩下一种情况,左右子树都不为空且值相等,可以开始递归判断 递归判断外侧-bool outside=compare(left->left,right->right); 递归判断内侧-bool inside=compare(left->right,right->left); 外侧和内存都为真才真,否则为假
class Solution {
public:
    bool compare(TreeNode*left,TreeNode*right){
        //左右子树都为空return true;
        if(left==nullptr&&right==nullptr){
            return true;
        //左右子树其中一个为空return false;
        }else if(left==nullptr||right==nullptr){
            return false;
        //左右子树都不为空但是值不相等return false;
        }else if(left->val!=right->val){
            return false;
        }
        //此时走到这,左右子树都不为空且值相等,可以开始递归
        //递归判断外侧
        bool outside=compare(left->left,right->right);
        //递归判断内侧
        bool inside=compare(left->right,right->left);
        bool issame=outside&&inside;
        return issame;


    }
    bool isSymmetric(TreeNode* root) {
        //上来先考虑特殊情况,root==nullptr直接return true;
        if(root==nullptr){
            return true;
        }
        //在子函数compare里递归解决
        return compare(root->left,root->right);
    }
};

上一篇:PAT 甲级 1006 Sign In and Sign Out


下一篇:对象比较的思考