预购和反向预购二叉树遍历

Question

我试图递归调用我的预订和反向预购方法。这些方法在基于数组的二叉树上工作，它们应该返回子树所有元素的长度。但是他们要做的是返回子树的第一个元素的长度。如果任何人都可以帮助它将不胜感激。

int left_width(vector<string>& vec, int i, int ret) { 
    int left = i * 2 + 1; 
    int right = i * 2 + 2; 
    ret = ret + vec[i].length(); 
    if (left < (int)vec.size() && right <= (int)vec.size()) { 
      left_width(vec, left, ret); 
      left_width(vec, right, ret); 
    } 
    return ret; 

}

int right_width(vector<string>& vec, int i, int ret) { 
    int right = i * 2 + 2; 
    int left = i * 2 + 1; 
    ret = ret + vec[i].length(); 
    if (left < (int)vec.size() && right <= (int)vec.size()) { 
      right_width(vec, right, ret); 
      right_width(vec, left, ret); 
    } 
    return ret; 

}

Answer 1

如果我明白你在做正确的东西，你需要从您的通话left_width或right_width获取返回值传递下去，让你累积所有通话。例如：

int right_width(vector<string>& vec, int i, int ret) { 
    int right = i * 2 + 2; 
    int left = i * 2 + 1; 
    ret = ret + vec[i].length(); 
    if (left < (int)vec.size() && right <= (int)vec.size()) { 
     ret = right_width(vec, right, ret); 
     ret = right_width(vec, left, ret); 
    } 
    return ret; 
} 

当然，传递作为参数通过计算线程这是一个“持续的返回值”还真是不地道的递归。通常你做更多的事情是这样的：

int right_width(vector<string>& vec, int i) { 
    int right = i * 2 + 2; 
    int left = i * 2 + 1; 
    int ret = vec[i].length(); 
    if (left < (int)vec.size() && right <= (int)vec.size()) { 
     ret += right_width(vec, right); 
     ret += right_width(vec, left); 
    } 
    return ret; 
} 

在这里，你刚刚从递归调用总结所有的返回值，用自己的本地值一起，然后将其返回给调用者。无需将工作进度计数传递给被调用者。