在二叉树中查找最长的偶数路径，return 所述路径的长度，非递归

Question

我必须创建一个算法来在不使用递归的情况下找到二叉树中偶数值的最长路径。例如，如果我的树如下： Binary Tree

算法应该return 3 因为那是唯一偶数值的最长路径的长度。

要求：

我们有两个队列可以使用
路径必须从根（给定的）开始

目前我的想法是：

使用Morris Traversal遍历树，但我不知道在代码的哪一部分进行“路径搜索”部分
不知何故，使用队列来保存相关节点，q1 将代表 tempLongestPath 和另一个 overallLongestPath.

但是我不清楚在遍历树时如何保存路径的长度。

在此先感谢您的帮助！

Answer 1

运行一个 BFS，假设树中只有偶数值并跟踪长度。

伪代码：

queue.put(root)
L[root] = 1
Max_L = -1
while !Queue.empty():
   current = queue.pull()
   if (current %2 ==1): SKIP/CONTINUE

   if Max_L < L[current]:
       Max_L = L[current]
   if current.left:
      queue.put(current.left)
      L[current.left] = L[current]+1
   if current.right:
      queue.put(current.right)
      L[current.right] = L[current]+1
return Max_L

如果你不想使用数组或一些合理的东西（即字典）来存储长度，你可以使用第二个队列来跟踪它们（做一个 put 而不是分配给 L 并做一个从 queue)

拉动时拉动

在二叉树中查找最长的偶数路径，return 所述路径的长度，非递归

Find longest even value path in binary tree, return length of said path, non-recursive

algorithm

binary-tree

data-structures