兩種遞歸方法之間的區別

我想反映一個二叉樹，使左邊的所有節點都結束在右邊，反之亦然。兩種遞歸方法之間的區別

喜歡的東西：

  A 
    / \ 
    B  C 
/ / \ 
D  E  F

將成爲

  A 
    / \ 
    C  B 
/\  \ 
F  E  D

我注意到，在寫我的解決方案，這個代碼工作：

static Tree getReflection(Tree root) { 
    if(root == null) { 
     return null; 
    } 
    Tree reflect = root; 
    Tree subRight = getReflection(root.right); 
    Tree subLeft = getReflection(root.left); 
    reflect.left = subRight; 
    reflect.right = subLeft; 
    return reflect; 
}

然而，這一次沒有按」 t：

static Tree getReflection(Tree root) { 
    if(root == null) { 
     return null; 
    } 
    Tree reflect = root; 
    reflect.left = getReflection(root.right); 
    reflect.right = getReflection(root.left); 
    return reflect; 
}

有人可以向我解釋爲什麼？對我來說，除了使用臨時樹變量外，它們看起來像是相同的方法。

來源

2016-03-02 Fiass

看看在每個第一條語句：當你將

反映=根

，這兩個變量現在都指向同一個內存位置。現在，讓我們來看看第二個程序的運行：

Tree reflect = root; 
// reflect and root now refer to exactly the same tree. 
reflect.left = getReflection(root.right); 
// reflect the right subtree; make that the new left subtree. 
reflect.right = getReflection(root.left); 
// Grab that new subtree, re-reflect it, and put it back on the right.

原來的左子樹丟失，由右側的反射所取代。

在第一個例程中，您將它們保存在局部變量中，直到完成兩次反射爲止。

來源

2016-03-02 02:21:09 Prune

所以我應該做一些像Tree reflect = new Tree（root.value）的東西。那麼它會創建一個新對象而不是指向原始根的指針？這個想法是否正確？ – Fiass

沒錯。你必須以某種方式得到新的副本，並且你的建議可以做到。 – Prune

這是因爲在第二個函數（不工作的函數）中，您將反射結果分配給您的左節點，然後將其用作您分配給右節點的反射的輸入。

樹反射= 根;

reflect.left = getReflection（root.right）;

reflect.right = getReflection（root.left）;

來源

2016-03-02 02:20:48 qexyn

兩種遞歸方法之間的區別

回答

相關問題