如何檢測二叉樹中的循環

Question

如何檢測二叉樹中的循環。作爲下圖中的一個例子，節點5是非法節點。一種方法是找到邊和節點的數量。邊緣應該是n -1。

Answer 1

你可以通過樹遍歷和檢查，如果每個家長都有兩個或更少數量的孩子，否則就不是一個二叉樹。

遞歸的方式：

flag = true; 
traverse(Node node){ 
    if(node == null || !flag) 
     return; 
    //Check for more than two children, if yes not binary tree, exit 
    if(node.getChilds().length > 2){ 
     flag = false; 
     return; 
    } 
    // Go through each nodes 
    for(Node child : node.getChilds()) { 
     traverse(child); 
    } 
} 

注：更好地將使用非遞歸的方式，在那裏你可以，只要你找到兩個以上的孩子退出循環。