题解 P5018 【对称二叉树】

· · 题解

其实本题的解题思路都差不多，但是要考虑清楚

程序主要部分：递归

-然而我听说这是一题水题

题目传送门

【题目解读】

看图，我们可以知道，对于题目给出的二叉树的子树中是否存在对称二叉树(当然这个子树可能是它自己)，可以判断：

  1. 结构不对称的不是；
  2. 权值不对称的不是；

然后针对这两种情况写一个递归边界；

接着还要考虑：两个对称位置的孩子节点都没有自己的孩子，那么这时递归也应该停止，返回此时节点数 +=0；否则，若没出现以上情况，那么每个节点有两个孩子节点，递归接下来对称的节点位置并把答案+2；

这里值得注意的是，这一题对称二叉树要整棵树对称，而不是子树自己对称，所以继续递归时代码要这么写：

    return dfs(lchild[i],rchild[j])+dfs(lchild[j],rchild[i])+2;

最左边的孩子节点和最右边的比较，以此类推。这样才能整棵树对称，而不是局部的对称。

那么代码实现也很简单：

  1. 定义标志变量，以便递归时判断是否为对称二叉树
  2. 答案 ans 初值设为 0，搜完最后输出的时候 +1 (第一、每颗树的父节点没有算；第二、如果没有搜到符合条件的树，那么每个个叶节点都是符合条件的“对称二叉树”，所以要 +1 )

以上就是全部思路，这样代码就很容易实现了。(为什么Dalao的代码那么长)

Code 
  //认真看，杜绝抄袭
  #include<iostream>
  #include<cstdio>
  #define MAX_N 1000005
  using namespace std;
  int n,lchild[MAX_N],rchild[MAX_N],w[MAX_N],ans=0;
  bool flag=true;
  int dfs(int i,int j)
  {
      if(i==-1 && j==-1)
      //左右孩子都没有自己的孩子了，没有接下来的节点
      //此时符合题目“对称二叉树”的定义 
        return 0;
      if((i==-1 || j==-1) && i!=j)
      //左孩子和右孩子有一个没有节点 结构不对称 
      {
          flag=false;
          return 0;
      }
      if(w[i]!=w[j])
      //权值不对称 
      {
          flag=false;
          return 0;
      }
      return dfs(lchild[i],rchild[j])+dfs(lchild[j],rchild[i])+2;
  }
  int main()
  {
      scanf("%d",&n);
      for(int i=1;i<=n;i++)
       scanf("%d",&w[i]);
      for(int i=1;i<=n;i++)
       scanf("%d%d",&lchild[i],&rchild[i]);
      for(int i=1;i<=n;i++)
      {
          int k=dfs(lchild[i],rchild[i]);//搜 
          if(flag)
          //flag为真 说明以第i个节点为父节点找到了对称二叉树 
          {
              ans=max(ans,k);
          }
          flag=true;
          //重置，以便下次运算 
      }
      printf("%d",ans+1);//结束时算上父根节点 
      return 0;
  }

总结ing

这题考的二叉树的基本知识和递归；