我最近被要求解决一个与二叉树遍历相关的问题，目的是找到二叉树中所有节点的和，其中节点是奇数，其叔叔也是奇数。我提出了一个解决方案，如下所示，算法复杂性为O(n((树的1次完全遍历(，辅助内存使用量等于O(h(。如果且仅当二叉树碰巧是BST和高度平衡的，则可以认为辅助记忆复杂性将是O(log(n((。
我的解决方案是所有根到叶问题的路径识别的变体。这个问题及其解决方案可以在这里找到。
https://github.com/anandkulkarnisg/BinaryTree/blob/main/set2/rootleaf.cpp
给出了具有奇叔的奇节点的解。
https://github.com/anandkulkarnisg/BinaryTree/blob/main/set5/sumodduncle.cpp
采访者同意算法的复杂性是显而易见的，因为肯定需要一次遍历，它是O(n(。但他认为辅助存储器的复杂性可以比O(h(设计得更好，他没有说明这种方法是什么。我已经考虑了两个星期了，还没有更好的解决方案。
我通过了面试，得到了一个我现在正在考虑的角色，但我仍然不知道辅助记忆调整的更好方法是什么。难道O(1(听起来是不可能的吗？直到我们在每个节点上都只跟踪父节点和祖父节点，这就是O(1，可能吗？
https://github.com/anandkulkarnisg/BinaryTree/blob/main/set5/sumodduncle.cpp在这个代码模块中，使用以下调用的解决方案。。。
long sumAlt=findSumOddUncle(uniqueBstPtr(
是O(1(解决方案，因为所有变量都通过指针传递，并且只传递总和，该总和在递归调用中累加。测试并按预期工作。