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

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;
    
    }