leetcode 스크립트 일기의 검증 두 갈래 검색 트리
3655 단어 알고리즘 노트
제목:
두 갈래 나무를 정해 효과적인 두 갈래 검색 나무인지 아닌지를 판단한다.
두 갈래 검색 트리에는 다음과 같은 정의가 있습니다.
。
。
。
예 1:
2 /\ 1 3
두 갈래 나무[2,1,3],true로 돌아갑니다.
예 2:
1 /\ 2 3
두 갈래 나무[1,2,3],false로 돌아갑니다.
문제 풀이 사고방식: 두 갈래 검색 트리의 순서가 반복되면 질서정연한 순서가 됩니다.따라서 이 성질을 빌려 이 두 갈래 검색 트리를 중순으로 훑어본 다음에 이 서열이 질서정연한지 판단하면 된다.
c++ 해법
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isValidBST(TreeNode* root) {
vector<int> v;
inOrder(root, v);
for (int i = 1; i < v.size(); i ++){
if (v[i - 1] >= v[i]) return false;
}
return true;
}
private:
void inOrder(TreeNode* root, vector<int> &v){//
if (root != NULL){
inOrder(root->left, v);
v.push_back(root->val);
inOrder(root->right, v);
}
}
};
python 해법
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def inOrder(self, root, arr):
if root:
self.inOrder(root.left, arr)
arr += [root.val]
self.inOrder(root.right, arr)
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
arr = []
self.inOrder(root, arr)
for i in range(1, len(arr)):
if arr[i-1] >= arr[i]:
return False
return True
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
leetcode 스크립트 일기의 검증 두 갈래 검색 트리두 갈래 나무를 정해 효과적인 두 갈래 검색 나무인지 아닌지를 판단한다. 두 갈래 검색 트리에는 다음과 같은 정의가 있습니다. 예 1: 두 갈래 나무[2,1,3],true로 돌아갑니다. 예 2: 두 갈래 나무[1,2...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.