如何减少以下两个二叉树相关问题的辅助内存：[祖父母和叔父相关问题]

Question

最近我被要求解决一个二叉树遍历相关问题，该问题的目的是找出二叉树中所有节点的和，其中节点是奇数，其叔父也是奇数。我给出的解决方案如下:算法复杂度(一次遍历树)中的O(n)和等于O(h)的辅助内存使用量。当且仅当二叉树发生BST和高度平衡时，则可以认为辅助记忆复杂度为O(log(n))。

我的解决方案是对所有根到叶问题的路径识别的变化。这个问题及其解决办法可以在这里找到。

本文给出了具有奇数叔父的奇数节点的解。

面试官同意算法的复杂性是显而易见的，因为一个遍历是绝对需要的，并且它是O(n)。但他认为，辅助记忆的复杂性可以设计得比O(h)好得多，而且他也不知道这种方法是什么。我已经考虑了两个星期了，还没有一个更好的解决方案。

顺便说一下，我批准了面试，并得到了一个我现在正在考虑的角色，但我仍然不知道在这里有什么更好的辅助内存调优方法。难道O(1)听起来是不可能的，直到我们在每个节点上只跟踪父和祖父母，即O(1).is才有可能？

Answer 1

https://github.com/anandkulkarnisg/BinaryTree/blob/main/set5/sumodduncle.cpp在此代码模块中使用以下调用的解决方案..。

sumAlt=findSumOddUncle(uniqueBstPtr);

是O(1)解决方案，因为所有变量都是通过指针传递的，并且只传递求和，它在递归调用中累加总数。测试并按预期工作。