[LeetCode] 671. 두 갈래 나무 중 두 번째로 작은 노드☆(귀속 합병)

묘사

비공식적이고 특수한 두 갈래 트리를 지정합니다. 노드마다 정수이고 노드마다 하위 노드의 수량은 2 또는 0만 가능합니다.만약 한 노드에 두 개의 하위 노드가 있다면, 이 노드의 값은 그것의 하위 노드의 값보다 크지 않다. 
이런 두 갈래 나무를 제시하려면 모든 노드 중의 두 번째 작은 값을 출력해야 한다.두 번째 작은 값이 존재하지 않으면 출력 -1.
예 1:
입력: 2/\2 5/\5 7
출력: 5 설명: 가장 작은 값은 2, 두 번째 작은 값은 5입니다.예 2:
입력: 2/\2
출력: -1설명: 가장 작은 값은 2이지만 두 번째 작은 값은 존재하지 않습니다.

해석

왼쪽 트리와 오른쪽 트리에서 node보다 더 큰 값을 찾습니다.두 개의 하위 나무가 각각 두 개의 값을 되돌려주면 가장 작은 것을 가져간다.

코드

public int findSecondMinimumValue(TreeNode root) {
        if (root == null || (root.left == null && root.right == null)) {
            return -1;
        }
        int left = -1;
        int right = -1;
        if (root.left != null) {
            left = root.left.val == root.val ? findSecondMinimumValue(root.left) : root.left.val;
        }
        if (root.right != null) {
            right = root.right.val == root.val ? findSecondMinimumValue(root.right) : root.right.val;
        }

        if (left != -1 && right != -1) {
            return Math.min(left, right);
        } else if (left != -1) {
            return left;
        } else if (right != -1) {
            return right;
        } else {
            return -1;
        }
    }

public int findSecondMinimumValue(TreeNode root) {
        if (root == null || (root.left == null && root.right == null)) {
            return -1;
        }
        List list = new ArrayList<>();
        findSecondMinimumValueH(root, list, root.val, Integer.MAX_VALUE);
        if (list.size() <= 0) {
            return -1;
        }
        int min = list.get(0);
        for (int li : list) {
            if (li < min) {
                min = li;
            }
        }
        return min;
    }

    public void findSecondMinimumValueH(TreeNode root, List list, int minVal, int moreVal) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            int value = root.left.val;
            if (value > minVal && value <= moreVal) {
                moreVal = value;// minVal ， 
                list.add(moreVal);
            } else {
                findSecondMinimumValueH(root.left, list, minVal, moreVal);
            }
        }

        if (root.right != null) {
            int value = root.right.val;
            if (value > minVal && value <= moreVal) {
                moreVal = value;// minVal ， 
                list.add(moreVal);
            } else {
                findSecondMinimumValueH(root.right, list, minVal, moreVal);
            }
        }
    }

이 코드는 첫 번째 코드와 약간 다르다. 모든 지점에 기록되어 있는데, 첫 번째는 루트보다 크다.val의 값을 찾아서 가장 작은 것을 찾아내면 두 번째로 크다.