驗證二叉樹中所有的數據項都等於

我使用Java進行二叉樹（不是二叉搜索樹）。我有類和實例變量聲明：驗證二叉樹中所有的數據項都等於

class intBTNode 
{ 
    private int data; 
    private intBTNode left; 
    private intBTNode right;

我想要做的就是寫一個返回true，只有樹中的所有條目等於目標數，或者如果樹是空的方法。我寫了下面的代碼：

public static boolean allEqual(intBTNode root, int target) 
{ 
    if (root == null) 
     return true; 
    if (root.data == target && root.left != null) 
     return allEqual(root.left, target); 
    if (root.data == target && root.right != null) 
     return allEqual(root.right, target); 
    return false; 
}

我想我的工作方式，通過這個來檢查代碼，但我不知道我充分檢查所有節點（即葉）的。此外，我試圖找出一種方法來攻擊這個問題是不是遞歸或會更有效。任何幫助或建議，將不勝感激。

來源

2016-09-24 Dustin

你是不是充分檢查所有節點。

的問題是，如果root.left非空，那麼你永遠不會檢查root.right;所以像這樣的樹：

 3 
    /\ 
    3 4

將被誤分類爲僅包含目標。

更好的方法是這樣寫：

public static boolean allEqual(intBTNode root, int target) 
{ 
    return root == null 
     || root.data == target 
      && allEqual(root.left, target) 
      && allEqual(root.right, target); 
}

如果你想避免因爲某些原因遞歸，你可以做，通過保持你已經「發現」節點的集合（通過訪問他們的父母），但還沒有真正「訪問」（通過檢查他們的data和兒童），並不斷拉結點出該集合，並探訪他們，直到它是空的：

public static boolean allEqual(intBTNode root, int target) 
{ 
    List<intBTNode> nodesToVisit = new ArrayList<intBTNode>(); 
    nodesToVisit.add(root); 
    while (! nodesToVisit.isEmpty()) { 
     intBTNode node = nodesToVisit.remove(nodesToVisit.size() - 1); 
     if (node == null) 
      continue; 
     if (node.data != target) 
      return false; 
     nodesToVisit.add(node.left); 
     nodesToVisit.add(node.right); 
    } 
    return true; 
}

（這實際上是完全等同於遞歸版本，只是使用ArrayList作爲堆棧，而不是使用調用堆棧。）

來源

2016-09-24 22:01:37 ruakh

此時應更換

if (root.data == target && root.left != null) 
    return allEqual(root.left, target); 
if (root.data == target && root.right != null)  
    return allEqual(root.right, target); 
return false;

隨着

return root.data == target && allEqual(root.left, target) && allEqual(root.right, target);

由於當前的代碼忽略右子樹（還有，空的檢查是多餘的，因爲你檢查每次如果根爲空）

至於避免遞歸，你可以使用不同的while循環，推動當前節點的孩子培養成一個堆（初始化與根）和不斷出現的第一個元素。（當然，雖然data == target）

來源

2016-09-24 21:54:02 eavidan

驗證二叉樹中所有的數據項都等於

回答

相關問題