LeetCode101.对称二叉树 C++(不使用STL库) + 递归算法的傻瓜讲解

• • 一、题目描述
  • 二、代码
  • 三、 提交结果
  • 四、递归的傻瓜例子
  • 五、代码解释

给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

提示：

    树中节点数目在范围 [1, 1000] 内
    -100 <= Node.val <= 100

class Solution {
public:
bool Travel(TreeNode*Rleft,TreeNode*Rright)
{
    if(Rleft==NULL&&Rright==NULL)return true;
    if(Rleft->left!=NULL^Rright->right!=NULL)return false;
    if(!Travel(Rleft->left,Rright->right))return false;
    if(Rleft->val!=Rright->val)return false;
    if(Rleft->right!=NULL^Rright->left!=NULL)return false;
    if(!Travel(Rleft->right,Rright->left))return false;
    return true;
}
    bool isSymmetric(TreeNode* root) {
return Travel(root,root);
    }
};

详细的递归算法讲解可以在CSDN查找，有几篇写的都特别好

这里简单的讲解一下递归，假如函数只有一个参数：bool Travel(TreeNode *Root）
二叉树如图：我们用递归算法判断是不是每一个结点值都小于5

//一开始我们代码是这样的
bool Travel(TreeNode *Root)
{//先不写}
bool isSymmetric(TreeNode* root) {
return Travel(root);
}

现在看Travel函数里面怎么写，因为这个二叉树每个节点都没有右节点，所以我们只遍历左边
想要遍历左边那么就得在bool Travel(TreeNode *Root) 里面调用自己这个travel函数，写成Travel(Root->left)

//一个没做完的递归
bool Travel(TreeNode *Root){
Travel(Root->left);
}
bool isSymmetric(TreeNode* root) {
return Travel(root);
}

可以明显的看出当 isSymmetric 调用Travel的时候他会一直沿着结点的左子树走下去
所以我们需要一个判断条件让它走到头（结点为空）时不往下走，并把结果返回，也就是要加个if()return语句
（先判断3号结点，再返回2号进行判断，最后回到1号）
为了完成题目要求还要判断结点值小于5

//这时可以知道我们利用true和false的传递来判断是不是每个结点的值都小于5
bool Travel(TreeNode *Root){
if（Root==NULL)return true;
Travel(Root->left);
if（root>=5)return false;
return true;
}
bool isSymmetric(TreeNode* root) {
return Travel(root);
}

接下来就是完成true和false值传递的工作，根据要求可以知道，如果有一个不符合条件return false,那么就不满足“所有数都小于5”，所以接下来都应该return false

//传递值
bool Travel(TreeNode *Root){
if（Root==NULL)return true;
if（！Travel(Root->left)）return false;
if（root>=5)return false;
return true;
}
bool isSymmetric(TreeNode* root) {
return Travel(root);
}

此时我们递归算法就写完了。假设三个结点值都小于5，大致流程如下：

写法是一开始的根节点左子树进行中序遍历和右子树进行镜像的中序遍历来判断是否对称
所以可以想成有两个指针RL和RR同时从根节点出发，RL：先左子树->根节点->右子树 RR：先右子树->根节点->左子树，这样两个指针指向的位置是对称的，我们需要判断指向的位置是否都有结点或都没有结点、都有结点时结点值是否相同

class Solution {
public:
bool Travel(TreeNode*Rleft,TreeNode*Rright)
{
    if(Rleft==NULL&&Rright==NULL)return true;
    if(Rleft->left!=NULL^Rright->right!=NULL)return false;
    if(!Travel(Rleft->left,Rright->right))return false;
    if(Rleft->val!=Rright->val)return false;
    if(Rleft->right!=NULL^Rright->left!=NULL)return false;
    if(!Travel(Rleft->right,Rright->left))return false;
    return true;
}

粗略讲讲代码：调用Travel(Rleft->left,Rright->right)最终会走到最左和最右的结点，此时有两种情况，对称则同时为NULL，不对称则一个是NULL一个不为NULL。
第二行为什么不拿RLEFT和RRIGHT判断（因为是好几个月前写的），但不影响，因为没这个判断是在调用自身函数递归的前一步，假设此时Travel函数中两个参数的指针位置如图所示（忽略上面的结点）：

因为所指结点都不为空且下个指向的位置也都对齐，所以经过时都不返回

if(Rleft==NULL&&Rright==NULL)return true;
if(Rleft->left!=NULL^Rright->right!=NULL)return false;
if(!Travel(Rleft->left,Rright->right))return false;

可以看出会调用Travel(Rleft->left,Rright->right)，此时指针指向如图所示：

还是这个代码：

if(Rleft==NULL&&Rright==NULL)return true;
if(Rleft->left!=NULL^Rright->right!=NULL)return false;
//此时下个位置结点不对称，返回false
if(!Travel(Rleft->left,Rright->right))return false;
//且只要有一次为false，就会一直传递false值

根据中序遍历，判断完左子树就判断根节点，再判断右子树（先判断结点位置是否对称，再判断值是否相等）

 if(Rleft->val!=Rright->val)return false;
 if(Rleft->right!=NULL^Rright->left!=NULL)return false;
 if(!Travel(Rleft->right,Rright->left))return false;
 return true;