java - 在树中搜索特定值

Question

我需要帮助使用 int 数据搜索二叉树(不一定是二叉搜索树)并查看树中是否有元素。如果它在树中，则返回引用，如果未找到，则返回 null。这是我到目前为止的代码。

Node search(TreeNode root, int key){
  if(root == null){
    return null;
    }  
   search(root.left, key);
   search(root.right, key); 

if(root.right.data === key || root.left.data == key){
     return root;
   }else{ 
      return null;
   }
}

Answer 1

您调用search(root.left, key);。太棒了。除非您正在搜索的元素确实位于当前节点的左分支中，否则不会发生任何情况。无论递归调用报告什么，该方法都会继续执行。您需要保留该数据并适当处理它。

因此你应该这样做:

Node search(TreeNode root, int key){
    if (root == null)
        return null;

    if (root.data == key)
        return root;

    Node n;

    n = search(root.left, key);
    if (n != null)
        return n;

    n = search(root.right, key);
    if (n != null)
        return n;

    return null;
}