[면접] 두 갈래 나무가 두 갈래 정렬 나무인지 아닌지 판단하다

3036 단어
1. 묘사
두 갈래 나무를 정하고, 한 그루 나무가 두 갈래 정렬 나무인지 아닌지를 어떻게 판단하는가.트리 결점의 정의는 다음과 같다.
class TreeNode {
    int key;
    TreeNode left;
    TreeNode right;

    public TreeNode(int key) {
        this.key = key;
    }
}

2. 문제 풀이 사고방식
두 갈래 정렬 트리의 성질에 따라 중서열을 반복할 때 현재 결점의 값은 항상 전구 결점의 값보다 크다. 전구 결점의 값을 반복할 때 보존해야 판단을 할 수 있고 이런 사고방식을 바탕으로 문제를 풀 수 있다.
코드
이상의 문제풀이 사고방식(반복할 때 두 갈래 정렬 트리의 성질을 이용)에 따라 다음과 같은 코드를 얻을 수 있다.
/**
 * Created by LEESF on 2016/9/8.
 */

class TreeNode {
    int key;
    TreeNode left;
    TreeNode right;

    public TreeNode(int key) {
        this.key = key;
    }
}

public class IsBSTree {
    static boolean flag = true;
    static int last = Integer.MIN_VALUE;

    public static boolean isBSTree(TreeNode root) {
        if (root.left != null && flag)
            isBSTree(root.left);
        if (root.key < last)
            flag = false;
        last = root.key;
        if (root.right != null && flag)
            isBSTree(root.right);
        return flag;
    }
}

좋은 웹페이지 즐겨찾기