圖像數據結構

Question

圖像（方形圖像）可以作爲樹存儲：如果圖像爲白色，則節點爲白色，如果圖像爲黑色，則爲黑色，如果圖像包含兩者，則爲混合。白色和黑色節點是葉子，而混合節點恰好有4個孩子，代表圖像中的4個象限。給定2個圖像（樹），找到代表它們相交的圖像。 （交叉點：B^B→B，B→W→W，W→W→W） 這是一個谷歌訪談問題

Answer 1

由於二者都表示爲二叉樹，所以必須遍歷樹結構從根開始，隨時檢查兩棵樹中節點的顏色，並將結果存儲在另一棵樹中。如果黑色或白色，則停止進一步移動。否則，如果它們中的任何一個在該節點中進一步混合遍歷，直到找到它們中的單個顏色。

Answer 2

下面是一個簡單的方法：使用相同的順序同時遍歷兩棵樹。當你這樣做的時候建立一個輸出樹。然後：

1. 如果你看到兩個樹混合節點，輸出混合節點
2. 如果你看到一棵樹混合節點，但在另一方面，輸出白色節點白色節點（而忽略遍歷中的混合節點）
3. 如果您在一棵樹中看到混合節點，而在另一棵樹中看到黑色節點，請將混合節點及其子節點複製到輸出樹
4. 如果看到兩個白色節點，白色節點
5. 如果看到兩個黑色節點，則輸出黑色節點

這有可能創建一個實際上只有白色孩子的混合節點，所以您可能需要一個壓縮步驟，在該步驟中遍歷樹摺疊只有白色孩子的混合節點。

編輯：我想你可以避免壓縮步驟，讓你的遞歸知道是否在下面找到輸出黑色節點（如果答案是否定的，則放入白色葉子）。