[Leet Code] Sum of Left Leaves 왼쪽 잎의 합.

문제

Find the sum of all left leaves in a given binary tree. 두 갈래 나무 한 그루를 정해서 그 모든 왼쪽 잎 노드의 값의 합을 찾아라.
Example:

    3
   / \
  9  20
    /  \
   15   7

There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.

생각하다

이 문제의 관건은 어떻게 모든 왼쪽 잎사귀 노드를 찾아내는가에 있다.한 그루의 두 갈래 나무에 대해 말하자면 그 모든 왼쪽 잎 노드를 찾으려면 내가 생각하는 가장 직접적인 방법은 이 두 갈래 나무를 두루 돌아다니며 방문한 노드가 왼쪽 잎 노드인지 그 값을 누적하는지 판단하면 답을 얻을 수 있다.

해법1

내 생각에 따르면, 이제 문제는 두 갈래 나무의 왼쪽 잎사귀 노드를 어떻게 두루 얻을 것인가로 옮겨졌다.한 그루의 두 갈래 나무를 두루 돌아다니면 자연스레 귀속 방식을 생각하게 된다. 왜냐하면 나무 자체가 귀속 구조이기 때문이다.
두 갈래 나무의 왼쪽 잎 노드는 왼쪽 나무와 오른쪽 나무에 존재할 수 있다.이 두 부분에서 각각 토론을 진행하여 왼쪽 잎 노드를 구한 다음에 더하면 원하는 것을 얻을 수 있다.

만약에 두 갈래 나무의 왼쪽 자목이 잎 노드라면 계속 깊이 들어갈 필요가 없다. 찾는 것이 바로 그것이다..

만약에 두 갈래 나무의 왼쪽 자목이 하나의 잎 노드가 아니라면, 이 과정을 반복해서 호출하여 왼쪽 자목의 왼쪽 잎 노드의 값을 얻습니다..

두 갈래 나무의 오른쪽 자나무에 대해서는 한 잎 노드든 결과에 영향을 주지 않으며, 직접 귀속 호출하여 오른쪽 자나무의 왼쪽 잎 노드 값을 가져오면 된다..

상기 귀속 사상에 따르면 코드는 다음과 같다.

public int sumOfLeftLeaves(TreeNode root) {
    if (root == null) return 0;// 
    int left, right;
    if (root.left != null && root.left.left == null 
        && root.left.right == null) {// 
        left = root.left.val;
    } else {
        left = sumOfLeftLeaves(root.left);
    }
    right = sumOfLeftLeaves(root.right);
    return left + right;
}

해법2

실제로 두 갈래 나무를 훑어보는 방식은 정말 너무 많다. 앞차례 훑어보기, 중간차례 훑어보기, 뒤차례 훑어보기, 등급별 훑어보기 등이다.두 갈래 나무를 두루 돌아다니는 것은 귀속적인 방식을 통해서도 되고, 교체되는 방식을 통해서도 된다.(필기시험 면접에서 나무의 비귀속을 자주 묻는다...=_=) 다음은 앞의 반복적인 방식으로 두 갈래 나무를 훑어보고 왼쪽 잎 노드의 값을 누적하여 문제를 해결한다.
코드는 다음과 같습니다.

public int sumOfLeftLeaves(TreeNode root) {
    TreeNode node = root;
    Stack stack = new Stack<>();
    int sum = 0;
    while (node != null || !stack.isEmpty()) {

        while (node != null) {
            stack.push(node);
            if (node.left != null && node.left.left == null 
                && node.left.right == null) {
                sum += node.left.val;
            }
                node = node.left;
        }

        if (!stack.isEmpty()) {
            node = stack.pop().right;
        }
    }
    return sum;
}

보조 창고를 통해 두 갈래 나무의 비귀속 전차를 실현하고 한 노드를 방문할 때 왼쪽 잎 노드인지 판단하면 된다.
다음은 두 갈래 나무를 층층이 훑어보는 방식으로 해답을 구하는 코드를 보여 줍니다.

public int sumOfLeftLeaves(TreeNode root) {
    if (root == null) return 0;
    Queue queue = new ArrayDeque<>();
    int sum = 0;
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        if (node.left != null && node.left.left == null 
            && node.left.right == null) {
            sum += node.left.val;
        }
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
    return sum;
}

사고방식은 일치한다. 단지 층층이 두루 돌아다니면서 하나의 보조 대열을 통해 실현해야 할 뿐이다.

총결산

사실 이 문제는 해결 방향을 생각하기 쉬우니 구화 문제를 두 갈래 나무를 두루 돌아다니는 문제로 바꾸면 된다.여기에 기록된 것도 두 갈래 나무의 몇 가지 역력 방식을 되돌아보기 위해서이다. 주로 비역귀적인 몇 가지 역력의 묘사법이다.