二叉搜索樹乘以-1的節點乘以

Question

考慮你有Binary Search Tree，如果是multiply all nodes by -1那麼任何人都可以讓我知道如果它仍然是Binary Search Tree？

是否可以編寫一個函數將其轉換回Binary Search Tree？

Answer 1

有趣的問題。

在Binary Search Tree中，對象圖的結構表示排序順序。

通過乘以-1的所有對象，它現在反向排序。

EG：

3 4 8 9 12 

成爲

-3 -4 -8 -9 -12 

---

那麼，如何才能讓這仍然維持二叉搜索樹的財產？

一棵二叉樹將由兩件事情組成：一個對象節點圖，以及如何比較對象的知識。比較函數會是這個樣子：

Compare(left, right) { 
    return (left < right); 
} 

如果您二叉樹內執行上的值轉換，你可以改變它的比較函數，然後它會繼續表現爲它應該。

myBinaryTree.comparisonFunction = function(left, right) { return (right < left) }; 

Answer 2

在二叉搜索樹中，節點左子樹的所有元素必須小於（或等於，在某些樹中）該節點，並且節點右子樹的所有元素必須大於（或等於，in一些樹）節點。如果將所有節點乘以-1，則最終會翻轉此節點，以便每個節點的左側子樹存儲更大的值，右側子樹存儲更小的值。爲了將其轉換回BST，您必須通過鏡像來「翻轉」BST。我將留下如何做這個練習的細節;這是一個經典的CS問題，帶有一個漂亮的遞歸解決方案。

希望這會有所幫助！