101. 对称二叉树

[Doragd]

• 101. 对称二叉树

• 给你一个二叉树的根节点 root， 检查它是否轴对称。
• 递归遍历+问题分解+分类讨论
  • 子结构: 两棵小树p和q, 同步遍历两棵树
  • 终止条件：p和q其中一方为空 或者 p 和 q不相等 return false
  • 否则: 递归判定: (左子树,右子树) (右子树,左子树)

class Solution {
public:
    //递归遍历+分类讨论:
    //子结构: 两棵小树p和q, 同步遍历两棵树
    //p和q其中一方为空 或者 p 和 q不相等 return false
    //否则: 递归判定: (左子树,右子树) (右子树,左子树)
    bool dfs(TreeNode *p, TreeNode *q){
        if(!p && !q) return true;
        if(p && q && p->val == q->val) return dfs(p->left, q->right) && dfs(p->right, q->left);
        return false;
    }
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return dfs(root->left, root->right);
    }
};