在泛型树中查找并返回具有下一个较大元素的节点

Question

我使用了一种不同的方法。但是只有两个测试用例成功运行。这是我的代码：

public static TreeNode<Integer> findNextLargerNode(TreeNode<Integer> root, int n){
Queue<TreeNode<Integer>>pendingNodes = new LinkedList<>();
pendingNodes.add(root);
if(root == null)
{
return null;
}
if(root.data > n)
{
return root;
}
while(pendingNodes.size()!=0)
{
TreeNode<Integer> front = pendingNodes.remove();
for(int i =0; i<front.children.size(); i++)
{
pendingNodes.add(front.children.get(i));
if(front.children.get(i).data > n)
{
return front.children.get(i);
}
}
}
return null;
}

我在哪里犯了错误？

Answer 1

考虑：

if(front.children.get(i).data > n)

通过这个if语句，将返回下一个更大的元素。

它适用于这样的情况：

21
10 3 20 30 40 2 40 50 0 0 0 0 

但是像这样的情况

21
10 3 20 20 40 2 40 30 0 0 0 0 

它将返回40，而我们需要30作为答案。

Answer 2

您的代码中有两个主要错误：

1. if(root.data > n) return root;考虑以下树：

   40
   /   
   10   30
   

   现在，如果在n=15的情况下运行函数，会发生什么？根大于n，因此返回40，而不是30作为所需输出。

2. if(front.children.get(i).data > n) return front.children.get(i);

   考虑以下示例：

   40
   /   
   20   18
   

   同样，在n=15的情况下运行，您将得到20，作为在根上检查的第一个子项。该函数返回，不再继续检查其他更合适的节点。

您的最简单的方法(当然不是最短的(可以使用以下算法来实现：

1. 遍历所有节点(BFS或DFS(并将数据导出到阵列
2. 查找n的下一个较大元素
3. 遍历树并找到包含该数据的节点

Answer 3

public static TreeNode<Integer> findNextLargerNode2(TreeNode<Integer> root, int n){
if(root==null) {return null;}
TreeNode<Integer> ans=null;
if(root.data>n) {
ans=root;
}
for(TreeNode<Integer> child: root.children) {
TreeNode<Integer> childans=findNextLargerNode2(child,n);
if(childans!=null) {
if(ans==null || ans.data>childans.data) {
ans=childans;
}
}
}
return ans;

}