左子樹小於右子樹

的深度的深度，我需要算法，在二叉樹爲每點頭檢查左子樹小於右子樹的深度的深度，返回true或false。它必須在O（n）中。左子樹小於右子樹

我想建立一個函數，計算每個子樹的深度，並使用它來檢查每個節點，如果左子樹的深度小於右子樹的深度，但我認爲這將是O（n^2 ）。

2014-09-20 mohamad rabee

您可以通過遞歸實現DFS的解決這個問題。 – uSeemSurprised 2014-09-20 19:58:40

這個問題似乎是無關緊要的，因爲它不是關於編程。請參閱幫助中心的[我可以詢問哪些主題]（http://stackoverflow.com/help/on-topic）。也許[計算機科學棧交換]（http://cs.stackexchange.com/）會是一個更好的地方。 – jww 2014-09-21 01:19:46

@jww你能指出一些關於[範圍頁面]（http://stackoverflow.com/help/on-topic）的特定文本，它認爲這是一個非主題？這不是一個非常詳細的問題，但它描述了一個特定的編程問題，提出了一個解決方案，並認識到解決方案不夠好。 – 2014-09-21 07:45:35

右：將最終爲O（n^2）。你需要通過深度優先搜索來做到這一點。編寫一個函數，確定以節點n爲根的子樹的深度。它需要一個節點，（遞歸地）詢問左側子樹的深度以及右側子樹的深度。返回一對(int, boolean)其中int是最大兩個子樹的深度，並且boolean是true如果左一個較小並且false如果不是。現在

你只是調用此您的根節點。它將遞歸地計算樹上每個節點的深度和平衡信息。

如果您可以更改節點並放入可用於註釋每個答案的字段，您可以在不返回一對的情況下執行此操作（如在u_seem_surprised的解決方案中）。但無論如何，現在是O（n）。

來源

2014-09-20 20:03:45

遞歸DFS解決方案：

struct node{ 
    int val; 
    bool leftGreater; 
    struct node *left, *right; 
}; 

int solve(Node *n){ 
    if(n == NULL){ 
     return 0; 
    } 
    int left = solve(n->left) + 1; 
    int right = solve(n->right) + 1; 
    if(left > right){ 
     n->leftGreater = true; 
    }else{ 
     n->leftGreater = false; 
    } 
return max(left, right); 
}

來源

2014-09-20 20:06:53 uSeemSurprised

左子樹小於右子樹

回答

相關問題