赞
踩
ybt 1981:【18NOIP普及组】对称二叉树
洛谷 P5018【NOIP2018 普及组】 对称二叉树
#include<bits/stdc++.h> using namespace std; #define N 1000005 typedef struct Node { int val, left, right;//val:权值, left:左孩子地址 right:右孩子地址 }Node; Node tree[N];//tree[i],为id为i的结点 int treeNodeNum[N];//treeNodeNum[i]保存id为i的结点的子树的结点数。 int n; int mxNodeNum;//结点数量最大的对称子树的结点数 //判断以root1为根的子树和以root2为根的子树是否对称 bool check(int root1, int root2) { if(root1 == -1 && root2 == -1)//空结点,相同 return true; else if(root1 != -1 && root2 != -1 && //左右子树都有结点 tree[root1].val == tree[root2].val && //树根结点权相同, treeNodeNum[root1] == treeNodeNum[root2] && //树结点数相同 check(tree[root1].left, tree[root2].right) && //经过对称变换后,root2树的右子树应该与root1树的左子树对称 check(tree[root1].right, tree[root2].left))//经过对称变换后,root2树的左子树应该与root1树的右子树对称 return true; else return false; } //获取树的结点数 int getNodeNum(int root) { if(root == -1) return 0; else { int nodeNum = getNodeNum(tree[root].left) + getNodeNum(tree[root].right) + 1; treeNodeNum[root] = nodeNum; return nodeNum; } } //确定结点最多的对称的子树的结点数 void Search(int root) { if(root != -1) { if(treeNodeNum[root] <= mxNodeNum)//剪枝,如果当前子树的结点数已经比获得的最大对称子树结点数要小,那么没必要再搜索下去。 return; if(check(tree[root].left, tree[root].right))//如果树root是对称的,那么其左右子树对称 mxNodeNum = treeNodeNum[root];//如果对称,记录结点数。由于已有剪枝操作,此时treeNodeNum[root]一定大于mxNodeNum else { Search(tree[root].left); Search(tree[root].right); } } } int main() { scanf("%d\n", &n); for(int i = 1; i <= n; ++i) scanf("%d", &tree[i].val); for(int i = 1; i <= n; ++i) scanf("%d %d", &tree[i].left, &tree[i].right); getNodeNum(1);//初始化树的各子树结点数 Search(1);//从根结点开始,遍历所有子树,找出对称子树,并看其结点数,保存最大结点数 printf("%d", mxNodeNum); return 0; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。