Saya sedang menulis sebuah program untuk mendapatkan Sum of depth untuk binaryTree yang diberikan. Ini mengembalikan nilai yang tepat dengan nilai instance tetapi mengembalikan nilai yang salah (lebih besar dari yang diharapkan) jika saya mencetak nilai yang dikembalikan dari metode. Kode dengan output seperti di bawah ini.
Catatan: Saya juga memiliki solusi yang tepat, tetapi saya memposting solusi ini untuk memahami apa yang salah dengan tumpukan panggilan rekursi. Harapan saya adalah di memori tumpukan terakhir, nilai akhir akan tetap ada yang akan dikembalikan ke metode pemanggil yang mengembalikan nilai yang berbeda.

public class NodeDepth_2 {

    static int sum = 0;
    
    public static int nodeDepths(BinaryTree root) {
        Integer depthSum = 0;
        Integer depth = -1;
        int finalValue = nodeDepths(root, depth, depthSum);
        System.out.println("Printing returned value from method: " + finalValue);
        System.out.println("sum from instance variable : " + sum);
        return depthSum.intValue();

    }

    public static int nodeDepths(BinaryTree root, int depth, int depthSum) {
        depth = depth + 1;
        depthSum = depthSum + depth;
        sum = sum + depth;


        if (root.left == null && root.right == null) {
            return depthSum;
        }

        return nodeDepths(root.left, depth, depthSum) + nodeDepths(root.right, depth, depthSum);

    }

    static class BinaryTree {

        int value;

        BinaryTree left;

        BinaryTree right;

        public BinaryTree(int value) {

            this.value = value;

            left = null;

            right = null;

        }

    }

    public static void main(String[] args) {
        BinaryTree root = new BinaryTree(1);

        root.left = new BinaryTree(2);

        root.left.left = new BinaryTree(4);
        root.left.left.left = new BinaryTree(8);

        root.left.left.right = new BinaryTree(9);

        root.left.right = new BinaryTree(5);

        root.right = new BinaryTree(3);

        root.right.left = new BinaryTree(6);

        root.right.right = new BinaryTree(7);

        nodeDepths(root);
    }

}

Keluarannya adalah:

Printing returned value from method: 21 // wrong value returned with method return
sum from instance variable : 16 // this is expected value
2
Nishant Bhardwaz 27 Mei 2021, 06:22

1 menjawab

Jawaban Terbaik

Kasus dasar harus mengembalikan depth daripada akumulasi depthSum.

Kasus dasar bertanya:

Berapa jumlah kedalaman subpohon yang tidak memiliki simpul anak?

Ini adalah depth dari subpohon itu! depthSum akan mencakup semua kedalaman simpul yang telah kita hitung, beberapa di antaranya tidak ada dalam subpohon yang kita tanyakan, jadi itu salah.

Selain itu, kasus rekursif juga harus menambahkan depth ke jumlah kedua subpohon.

Kasus rekursif bertanya:

Berapa jumlah kedalaman subpohon dengan dua sub-subpohon?

Ini adalah jumlah jumlah kedalaman dari sub-subpohon tersebut, ditambah kedalaman dari subpohon itu sendiri!

Perhatikan juga bahwa Anda lupa kasus ketika salah satu dari root.left dan root.right adalah nol.

Setelah menangani kasus-kasus itu, kodenya akan terlihat seperti:

public static int nodeDepths(BinaryTree root, int depth, int depthSum) {
    depth = depth + 1;
    depthSum = depthSum + depth;
    sum = sum + depth;

    int retVal = depth;

    if (root.left != null) {
        retVal += nodeDepths(root.left, depth, depthSum);
    }

    if (root.right != null) {
        retVal += nodeDepths(root.right, depth, depthSum);
    }

    return retVal;

}
0
Sweeper 27 Mei 2021, 05:33