두 갈래 나무의 BST 여부를 판단하다

1. 질문:
함수를 실현하여 두 갈래 나무가 두 갈래인지 확인하십시오.트리의 루트 결점 포인터인 TreeNode*root를 지정합니다. 이 트리가 두 갈래인지 아닌지를 나타내는 bool로 돌아가십시오.
2. 생각:
해법1: 뿌리 노드에서부터 두 갈래 나무를 훑어본다. 그 중에서 차례대로 노드를 훑어보고 뿌리의 좌우 노드의 값과 뿌리 노드의 값의 크기를 판단해야 한다. 그 중에서 차례대로 돌아가는 사고방식은 만약에 나무가 왼쪽 나무가 있다면 우리는 왼쪽 나무, 오른쪽 나무가 있으면 오른쪽 나무, 왼쪽 나무가 있으면 우리는 왼쪽 나무를 훑어보고 잎 노드가 될 때true로 돌아가면 된다.위의 판단을 제외하고는 부족하기 때문에 왼쪽 트리에서 가장 큰 노드 값이 루트 노드의 값보다 작고, 오른쪽 트리에서 가장 작은 노드의 값이 루트 노드의 값보다 큰지 판단해야 한다.
해법2: 우선 우리가 생각한 것은 두 갈래 나무에서 차례대로 훑어본 결과가 질서정연하다는 것이다. 이 결과에 따라 우리는 두 갈래 나무를 차례대로 훑어보고 그 결과를 한 수조에 저장한 다음에 이 수조의 크기가 질서수조인지 아닌지를 판단할 수 있다. 만약에 질서수조라면 두 갈래로 나무를 찾을 수 있다. 그렇지 않으면 그렇지 않다.이 방법의 시간 복잡도는 O(N)이지만 공간 복잡도가 비교적 높아 O(N)의 저장 공간을 낭비해야 한다.

import java.util.ArrayList;

public class CheckBST1 {
    //  
    public boolean checkBST(TreeNode root) {
        if (root == null)
            return false;
        ArrayList list = new ArrayList<>();
        inorder(root, list);
        return checkOrdered(list);
    }

    //  
    private void inorder(TreeNode node, ArrayList list) {
        if (node == null)
            return;
        if (node.left != null) {
            inorder(node.left, list);
        }
        list.add(node.val);
        if (node.right != null) {
            inorder(node.right, list);
        }
    }

    //  ， ， ， false
    private boolean checkOrdered(ArrayList list) {
        for (int i = 0; i < list.size() - 2; i++) {
            if (list.get(i) > list.get(i + 1))
                return false;
        }
        return true;
    }

    public static class TreeNode {

        public T val;
        public TreeNode left = null;
        public TreeNode right = null;
        public TreeNode parent = null;

        public TreeNode(T val) {
            this.val = val;
        }

    }
}

해법 3: 전역 변수는 이전 값을 기록하고 현재 값은 이전 값보다 커야 합니다.조건을 충족시키면pre를 현재 값으로 업데이트합니다.

 1 public class CheckBST2 {
 2     public boolean checkBST(TreeNode root) {
 3         if (root == null)
 4             return true;
 5 
 6         //  ， bst false
 7         boolean leftIsBST = checkBST(root.left);
 8         if (!leftIsBST)
 9             return false;
10         //  ， false
11         if (root.val <= preValue) {
12             return false;
13         }
14         //  ， 
15         preValue = root.val;
16         return checkBST(root.right);
17     }
18 
19     private int preValue = Integer.MIN_VALUE;
20 
21     public static class TreeNode {
22 
23         public T val;
24         public TreeNode left = null;
25         public TreeNode right = null;
26         public TreeNode parent = null;
27 
28         public TreeNode(T val) {
29             this.val = val;
30         }
31 
32     }
33 }