두 갈래 나무 모층 노드의 합

위의 문장의 계발에 근거하여 나는 스스로 한 문제를 생각했다.두 갈래 나무의 노드 중의 수치가 모두 정수라고 가정하고 어떤 층의 노드 수의 합을 구한다.루트 노드는 첫 번째 층이다.이 레이어가 없으면 -1로 돌아갑니다.가장 간단한 방법은 다음과 같다.

private static int cnt = 0;

public void sumOfLevel(BinaryTreeNode root, final int level, int cur) {
    if (root == null) {
        return;
    }
    if (cur == level) {
        cnt += root.value;
        return;
    }

    if (root.left != null) {
        sumOfLevel(root.left, level, cur + 1);
    }

    if (root.right != null) {
        sumOfLevel(root.right, level, cur + 1);
    }
}

cur의 초기값은 1입니다.그러나 이런 작법은 두 가지 방법을 써야 하고, 다른 하나는 cnt를 되돌려야 한다.방법 하나만 써주시면 안 돼요?

public int sumOfLevel(BinaryTreeNode root, final int level, int cur) {
    if (root == null) {
        return -1;
    }
    if (cur == level) {
        return root.value;
    }

    int leftValue = sumOfLevel(root.left, level, cur + 1);
    int rightValue = sumOfLevel(root.right, level, cur + 1);
    if (leftValue < 0 && rightValue < 0) {
        return -1;
    }
    leftValue = leftValue < 0 ? 0 : leftValue;
    rightValue = rightValue < 0 ? 0 : rightValue;
    return leftValue + rightValue;
}

2019-02-26 다시보기: 제목을 받고 다음 코드를 썼습니다.

    int sum(BinaryTreeNode root, final int level, int cur) {
        if (root == null || cur > level) {
            return 0;
        }
        int value = 0;
        if (cur == level) {
            value = root.value;
        }
        return value + sum(root.left, level, cur + 1) 
                + sum(root.right, level, cur + 1);
    }

이 코드는 매우 간결한데, 알고리즘은 두 갈래 나무의 뒷부분을 두루 훑어보는 것이다.그러나 이 층이 존재하지 않으면 0으로 되돌아간다는 점은 제목에 부합되지 않는다.이 코드를 사용하려면 나무의 높이를 미리 계산하고 차원이 존재하는지 아닌지를 판단해야 하는데 너무 우아하지 않다.

    int sum(BinaryTreeNode root, final int level, int cur) {
        if (root == null || cur > level) {
            return -1;
        }
        if (cur == level) {
            return root.value;
        }

        int left = sum(root.left, level, cur + 1);
        int right = sum(root.right, level, cur + 1);
        if (left < 0 && right < 0) {
            return -1;
        }
        left = left < 0 ? 0 : left;
        right = right < 0 ? 0 : right;
        return left + right;
    }

sum () 은 루트를 루트로 하고cur층의 합을 나타낸다.cur=height, 그러면 root로 바로 돌아갑니다.value는 됩니다. 계속 귀속할 필요가 없습니다.이렇게 하면cur>height의 상황을 피할 수 있다.