【題目鏈接】

ybt 1981：【18NOIP普及組】對稱二叉樹
洛谷 P5018【NOIP2018 普及組】 對稱二叉樹

【題目考點】

二叉樹

【解題思路】

先求出二叉樹中各子樹的結點數

遍歷二叉樹，判斷每個子樹是否是對稱二叉樹

• 判斷一個二叉樹是否是對稱二叉樹：
• 對稱變換：將該樹中所有結點的左右子樹交換。顯然，一棵樹經過兩次對稱變換后，會變為原來的樹。
• 兩樹對稱：如果樹1經過對稱變換可以變為樹2，那么稱樹1與樹2對稱。顯然，樹1與樹2對稱時，樹2與樹1對稱。
• 如果一個二叉樹是對稱二叉樹，那么其左子樹應該與右子樹對稱。
  • 證明：二叉樹是對稱的，那么其經過對稱變換后的左子樹，是由原右子樹變換過來的。已知對稱變換后的樹與原樹相同，那么變換后的左子樹與原左子樹相同，那么原左子樹與原右子樹是對稱的。
• 設函數check()，參數為樹1、樹2兩棵樹的根，該函數判斷樹1、樹2是否對稱。
• 判斷兩棵樹是否對稱：
  • 如果兩棵樹都是空樹（根結點地址都為-1），那么它們是對稱的。
  • 如果兩棵樹都不是空樹，同時滿足如下條件時，二者才是對稱的
    • 兩棵樹根結點的權值應該相同
    • 兩棵樹的結點數應該相同
    • 樹1的左子樹應該與樹2右子樹對稱。
    • 樹1的右子樹應該與樹2的左子樹對稱

【題解代碼】

解法1：

#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;elsereturn 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]一定大于mxNodeNumelse{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; }

總結

以上是生活随笔為你收集整理的信息学奥赛一本通 1981：【18NOIP普及组】对称二叉树 | 洛谷 P5018【NOIP2018 普及组】 对称二叉树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。