C++LeetCode 구현(98.두 갈래 검색 트 리 검증)

[LeetCode]98.바 이 너 리 검색 트 리 검증
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node's key.

The right subtree of a node contains only nodes with keys greater than the node's key.

Both the left and right subtrees must also be binary search trees.

Example 1:
Input:
2
/ \
1   3
Output: true
Example 2:
    5
/ \
1   4
/ \
3   6
Output: false
Explanation: The input is: [5,1,4,null,null,3,6]. The root node's value
is 5 but its right child's value is 4.
이 검증 이 진 트 리 는 여러 가지 해법 이 있 습 니 다.그 자체 의 성질 을 이용 하여 할 수 있 습 니 다.즉,왼쪽<뿌리<오른쪽,중간 순 서 를 이용 하여 결 과 를 질서 있 는 수열 로 옮 길 수 있 습 니 다.다음은 우리 가 먼저 가장 간단 한 것 은 그 자체 의 성질 을 이용 하여 하 는 것 입 니 다.초기 화 할 때 시스템 의 최대 치 와 최소 치 를 가 져 와 재 귀 과정 에서 그들의 노드 값 으로 바 꾸 는 것 입 니 다.int 대신 log 를 사용 하 는 것 은 int 의 경계 조건 을 포함 하기 위해 서 입 니 다.코드 는 다음 과 같 습 니 다.
C++해법 1:

// Recursion without inorder traversal
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return isValidBST(root, LONG_MIN, LONG_MAX);
    }
    bool isValidBST(TreeNode* root, long mn, long mx) {
        if (!root) return true;
        if (root->val <= mn || root->val >= mx) return false;
        return isValidBST(root->left, mn, root->val) && isValidBST(root->right, root->val, mx);
    }
};

자바 해법 1:

public class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        return valid(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    public boolean valid(TreeNode root, long low, long high) {
        if (root == null) return true;
        if (root.val <= low || root.val >= high) return false;
        return valid(root.left, low, root.val) && valid(root.right, root.val, high);
    }
}

이 문 제 는 실제 적 으로 난이 도 를 간소화 했다.왜냐하면 어떤 때 는 문제 중의 이 진 트 리 가 왼쪽<=뿌리<오른쪽>으로 정의 되 기 때문이다.이 문 제 는 일반적인 상황 에서 왼쪽<뿌리>오른쪽 으로 설정 하면 중간 순서 로 역대로 풀 수 있 기 때문이다.왼쪽=루트 라 는 조건 을 제거 하지 않 으 면 아래 두 개의 수 를 중간 순서 로 옮 겨 다 니 며 구분 할 수 없 기 때 문 입 니 다.
   20       20
/           \
20           20
이들 의 중간 순 서 는 모두 같 지만 왼쪽 은 BST 이 고 오른쪽 은 BST 가 아니다.등 호 를 없 애 는 조건 은 이런 제한 조건 을 없 애 는 것 과 같다.다음은 중 서 를 사용 하여 역대로 하 는 것 을 보 겠 습 니 다.이런 방법 은 사고방식 이 매우 직접적 입 니 다.중 서 를 통 해 모든 노드 값 을 한 배열 에 저장 한 다음 에 이 배열 이 질서 가 있 는 지 판단 하 겠 습 니 다.코드 는 다음 과 같 습 니 다.
C++해법 2:

// Recursion
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if (!root) return true;
        vector<int> vals;
        inorder(root, vals);
        for (int i = 0; i < vals.size() - 1; ++i) {
            if (vals[i] >= vals[i + 1]) return false;
        }
        return true;
    }
    void inorder(TreeNode* root, vector<int>& vals) {
        if (!root) return;
        inorder(root->left, vals);
        vals.push_back(root->val);
        inorder(root->right, vals);
    }
};

자바 해법 2:

public class Solution {
    public boolean isValidBST(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        inorder(root, list);
        for (int i = 0; i < list.size() - 1; ++i) {
            if (list.get(i) >= list.get(i + 1)) return false;
        }
        return true;
    }
    public void inorder(TreeNode node, List<Integer> list) {
        if (node == null) return;
        inorder(node.left, list);
        list.add(node.val);
        inorder(node.right, list);
    }
}

아래 의 이러한 해법 은 위 에 있 는 것 과 매우 유사 합 니 다.모두 재 귀적 인 중간 순서 로 옮 겨 다 니 지만 다른 점 은 옮 겨 다 니 는 결 과 를 한 배열 에 저장 하지 않 고 새로운 노드 에 옮 겨 다 닐 때마다 이전 노드 와 비교 하 는 것 입 니 다.이전 노드 보다 크 지 않 으 면 false 로 돌아 가 고 모든 것 이 완 료 된 후에 true 로 돌아 갑 니 다.코드 는 다음 과 같 습 니 다:
C++해법 3:

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        TreeNode *pre = NULL;
        return inorder(root, pre);
    }
    bool inorder(TreeNode* node, TreeNode*& pre) {
        if (!node) return true;
        bool res = inorder(node->left, pre);
        if (!res) return false;
        if (pre) {
            if (node->val <= pre->val) return false;
        }
        pre = node;
        return inorder(node->right, pre);
    }
};

물론 이 문 제 는 비 재 귀적 으로 도 풀 수 있 습 니 다.스 택 을 사용 해 야 합 니 다.중간 순 서 는 재 귀적 으로 이 루어 지지 않 을 수 있 기 때문에 그 위 에 조금 만 바 꾸 면 됩 니 다.코드 는 다음 과 같 습 니 다.
C++해법 4:

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> s;
        TreeNode *p = root, *pre = NULL;
        while (p || !s.empty()) {
            while (p) {
                s.push(p);
                p = p->left;
            }
            p = s.top(); s.pop();
            if (pre && p->val <= pre->val) return false;
            pre = p;
            p = p->right;
        }
        return true;
    }
};

자바 해법 4:

public class Solution {
    public boolean isValidBST(TreeNode root) {
        Stack<TreeNode> s = new Stack<TreeNode>();
        TreeNode p = root, pre = null;
        while (p != null || !s.empty()) {
            while (p != null) {
                s.push(p);
                p = p.left;
            }
            p = s.pop();
            if (pre != null && p.val <= pre.val) return false;
            pre = p;
            p = p.right;
        }
        return true;
    }
}

마지막 으로 한 가지 방법 이 있 습 니 다.중간 순서 가 반복 되 지 않 고 스 택 이 없 는 실현 방법 이 있 기 때문에 Morris 가 옮 겨 다 니 는 것 이 라 고 부 릅 니 다.블 로 거 이전의 블 로 그 를 참고 할 수 있 습 니 다.  Binary Tree Inorder Traversal이런 실현 방법 은 재 귀 버 전보 다 복잡 하 게 쓰 이지 만 장점 은 O(1)공간 복잡 도 이다.코드 는 다음 과 같다.
C++해법 5:

class Solution {
public:
    bool isValidBST(TreeNode *root) {
        if (!root) return true;
        TreeNode *cur = root, *pre, *parent = NULL;
        bool res = true;
        while (cur) {
            if (!cur->left) {
                if (parent && parent->val >= cur->val) res = false;
                parent = cur;
                cur = cur->right;
            } else {
                pre = cur->left;
                while (pre->right && pre->right != cur) pre = pre->right;
                if (!pre->right) {
                    pre->right = cur;
                    cur = cur->left;
                } else {
                    pre->right = NULL;
                    if (parent->val >= cur->val) res = false;
                    parent = cur;
                    cur = cur->right;
                }
            }
        }
        return res;
    }
};

C++구현 LeetCode(98.검증 이 진 트 리)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 검증 이 진 트 리 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 도 많은 응원 부 탁 드 리 겠 습 니 다!