Java тест два бинарных деревьев одинаковы

Question

Update: Лучшее решение должно быть:

public boolean isSameTree(TreeNode p, TreeNode q) { 

    if(p==null&&q==null) return true; 
    if(p==null||q==null) return false; 

    return isSameTree(p.left, q.left)&&isSameTree(p.right, q.right)&&(p.val==q.val); 
} 

---

Обновление: Спасибо всем, я знаю, что эти другие решения, которые вы сказали мне, но мой вопрос почему мое решение не работает. Это потому, что я игнорирую некоторые возвращаемые значения? Спасибо!

---

Я написал код для определения, являются ли два бинарных деревьев одни и те же, я использовал рекурсивный метод для поиска по дереву, но этот код иногда не работает, не могли бы вы помочь мне понять это ?

Большое спасибо! Вот код:

/*Definition for a binary tree node. 
    public class TreeNode { 
    int val; 
    TreeNode left; 
    TreeNode right; 
    TreeNode(int x) { val = x; } 
*/ 

public boolean isSameTree(TreeNode p, TreeNode q) { 
    if(p!=null){ 
     if(q!=null&&p.val==q.val){ 
      isSameTree(p.left, q.left); 
      isSameTree(p.right, q.right); 
     } 
     else return false; 
    }else{ 
     if(q!=null) return false; 
    } 
    return true; 
} 

Вход: [10,5,15] [10,5, NULL, NULL, 15] Выход: истинный Ожидаемое: ложные

Answer 1

Вы просто вызывает isSameTree для дочерних деревьев, но не проверяет их возвращаемые значения. Сжатый и правильная версия:

public boolean isSameTree(TreeNode p, TreeNode q) { 
    if (p == q) { //Will accept null == null 
     return true; 
    } 
    return p != null && q != null && p.val == q.val && 
     isSameTree(p.left, q.left) && isSameTree(p.right, q.right); 
} 

Кроме того, @duffymo было неправильным указанием вам необходимо использовать .equals() вместо ==. Вы сравниваете val, которые являются примитивами.

Answer 2

public boolean isSameTree(TreeNode p, TreeNode q) { 
     if(p!=null){ 
      if(q!=null&&p.val==q.val){ 
       if(!isSameTree(p.left, q.left)) return false; 
       if(!isSameTree(p.right, q.right)) return false; 
       return true; 
      } 
      else return false; 
     }else{ 
      if(q!=null) return false; 
     } 
     return true; 
    } 

Answer 3

Я предполагаю, что у вас есть метод GET для извлечения data.One образом, вы можете решить это позволить методы isSameTree принимать нулевые значения, а затем сравнить.

public boolean isSameTree(TreeNode p, TreeNode q) { 

     if (p == q) { 
      return true; 
     } 
     if (p == null || q == null) { 
      return false; 
     } 

     return p.get().isSameTree(q.get()) && 
       isSameTree(p.left(), q.left()) && 
       isSameTree(p.right(), q.right()); 
    } 

Другой способ заключается в следующем:

public boolean isSameTree(TreeNode p, TreeNode q) 
    { 

     if (p == null && q == null) 
      return true; 


     if (p != null && q != null) 
      return (p.get == q.get 
        && isSameTree(p.left, q.left) 
        && isSameTree(p.right, q.right)); 


     return false; 
    }