我需要找出可以結束的二叉樹的所有路徑（這意味著從根開始并結束到只有一個子節點或沒有子節點的所有路徑）的長度差異不超過一。
我的作業解決方案是這樣作業的：函式longestPath 找到最長的路徑，函式checkLengths 遍歷所有節點，跟蹤路徑的長度，每次發現只有一個或沒有一個子節點的節點時，它檢查長度之間的差異當前路徑和最長路徑的長度大于1。
該解決方案的復雜度為 O(2n)，因為在最壞的情況下，每個節點都必須被訪問兩次，一次是針對最長路徑函式，一次是針對 lengthCheck 函式。我想改進 O(n) 的解決方案，但我很難弄清楚如何去做。
編輯：我的解決方案仍然是 O(n) 但我想通過僅訪問每個節點一次而不是兩次來優化它以找到解決方案。
int lengthCheckFlag=1;
int maxLength=-1;
void longestPath(Node n,int currentLength){
if(n==nullptr){
return;
}
if(n->left==nullptr && n->right==nullptr){
if(maxLength==-1){
maxLength=currentLength;
}
else{
if(currentLength>maxLength){
maxLength=currentLength;
}
}
}
longestPath(n->left,currentLength 1);
longestPath(n->right,currentLength 1);
}
void checkLengths(Node n,int currentLength){
if(n==nullptr){
return;
}
if(n->left==nullptr || n->right==nullptr){
if(abs(maxLength-currentLength)>1){
lengthCheckFlag=0;
}
}
checkLengths(n->left,currentLength 1);
checkLengths(n->right,currentLength 1);
}
bool lengthCheckWrapper(Node n){
if(n==nullptr){
return true;
}
longestPath(n,0);
checkLengths(n,0);
return lengthCheckFlag;
}
代碼更新：
int maxP=-1;
int minP=-1;
void minmaxPaths(Node n,int currentLength){
if(n==nullptr){
return;
}
if(n->left==nullptr && n->right==nullptr){
if(maxP==-1){
maxP=currentLength;
minP=currentLength;
}
else{
if(currentLength>maxP){
maxP=currentLength;
}
if(currentLength<minP){
minP=currentLength;
}
}
}
minmaxPaths(n->left,currentLength 1);
minmaxPaths(n->right,currentLength 1);
}
bool lengthCheckWrapper(Node n){
if(n==nullptr){
return true;
}
minmaxPaths(n,0);
if(abs(minP-maxP)<=1){
return true;
}
return false;
}
uj5u.com熱心網友回復：
一些備注：
- O(2n) 與 O(n) 相同
- 您的函式使用不同的條件來識別路徑的潛在終點：一個使用
&&運算子（錯誤），另一個使用||運算子（正確）
替代演算法的一個想法是進行廣度優先遍歷。這很有趣，因為約束實際上意味著所有非完美節點（即最多有一個子節點）必須出現在樹的底部兩層。
因此，如果我們在發現非完美節點的第一個級別之后再找到 2 個級別，那么我們就有了違規并且可以停止遍歷。
不利的一面是它使用更多的記憶體。
以下是它的實作方式：
int minmaxDepth(Node root) {
if (root == nullptr) {
return 1; // OK
}
std::vector<Node> level, nextLevel;
level.push_back(root);
int minDepth = INT_MAX;
int currDepth = 0;
while (level.size()) {
currDepth ;
nextLevel = {};
for (auto & parent : level) {
if (currDepth < minDepth &&
(parent->left == nullptr || parent->right == nullptr)) {
minDepth = currDepth; // Found a path with minimal length
}
if (parent->left != nullptr) {
nextLevel.push_back(parent->left);
}
if (parent->right != nullptr) {
nextLevel.push_back(parent->right);
}
if (nextLevel.size() && currDepth > minDepth) {
return 0; // Paths have lengths that differ more than 1
}
}
level = nextLevel;
}
return 1; // All nodes were visited: no violation found
}
uj5u.com熱心網友回復：
無需預先計算最長路徑。計算所有路徑長度并即時計算，
存盤第一個長度，
如果其他長度相差不止一個，你就完成了；
else 存盤不同的長度，如果任何其他長度與兩個存盤的長度不同，你就完成了。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/380276.html