德摩根定律與Symmetric Tree

來自專欄大學生學C語言1 人贊了文章

主動來學計算機的學生，骨子裡大多都有一種「經世致用」的勁頭。這種勁頭功利了一點，但也無可厚非。可往往會和學校的規矩起衝突，比如一些思想政治課的老師我就不是很喜歡，說的好聽一點，叫「嚴肅有餘，活潑不足」，說的難聽點……我就不說了

這種心思多了，就會變得浮躁。我現在開始上概率論的課，上著上著，就發現了我的老朋友：德摩根定律。為什麼說是老朋友呢，很簡單，我模擬與數字電路 學到他，離散數學 學到他，現在概率論我還得再學一遍，連馬甲都不帶換的。

當然，這一定程度上也說明了：知識是相通的這個觀點。但我學了這麼多遍，在計算機里的應用我還一點都不知道，這就有點說不過去了。好在過了幾天，我刷到了一道叫做：Symmetric Tree的題目，才有點明白為什麼要一遍遍學這玩意兒。

題目很簡單：Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

1

2 2

But the following[1,2,2,null,3,null,3]is not:

1

/

題目很簡潔，一看就是用遞歸。

（這裡就不得不吐槽一下研究生考試里的：用非遞歸的方法搞樹……你先搞一個棧再搞一個while循環難道就不是遞歸了？你騙誰呢）

思路也很簡單，先判斷是不是空的樹，在遞歸循環檢查子節點。左子樹和右子樹都是空的可以，一邊空一邊不空不行，兩邊都不空必須值一樣。

然後就正常打下代碼 if……else if……else……但刷題有一點很關鍵：要會認慫。果斷去看vote數比較高的代碼，然後我就看到了這個：

if (p == NULL || q == NULL) return (p == q);

一拍大腿，嘿，你還別說，這洋鬼子的鬼點子還真多！

但我隨後意識到，這不是鬼點子，而是用布爾代數列舉出所有情況，再用一系列包括德摩根定律推導出來的東西。擺脫了 if……else 所造成的尷尬，既解決了代碼冗長的問題，又增加了可讀性。我又自己用離散數學課上學到的東西推導了一邊，最後我的答案是這樣：

class Solution {public: bool isSymmetric(TreeNode* root) { if(!root) return true; return helper(root->left,root->right); } bool helper(TreeNode* p,TreeNode* q){ return (!p && !q)||(q && p && q->val == p->val && helper(p->left,q->right) && helper(p->right,q->left)); }};

推導的紙找不到了，雖然這個可能更加「短」，但是犧牲了一些可讀性。有興趣的同學可以自己試試看。

最後說一句，我以前打發時間，看過一本叫《花與劍與法蘭西》的小說。裡面我記得清楚的一點是：名字裡帶著一個「德」的人，往往是貴族或是貴族的後裔。我懶的去查資料，但我想德摩根能成為一個數學家，他貴族身份所能爭取到的良好的教育條件，一定起了很大作用。我們生活在和平年代，國家好歹還算是社會主義國家，能多學點知識，不要不知好歹。就像《倚天屠龍記》裡面謝遜說的：「你現在不管懂不懂先記下，以後自有你的好處。」我自己也覺得除開 有 點 問 題 的思修馬克思老師，政治課書本上的內容還是很有道理的，很有用的。如果大家都能有點唯物史觀，現在這個社會就不會這麼亂了。