LeetCode ---　Validate Binary Search Tree

제목 링크
두 갈래 나무가 두 갈래 검색 트리 (두 갈래 정렬 트리), 즉 BST 인지 아닌지 판단하기
만약 이 두 갈래 나무가 BST라면, 그 속의 서열을 두루 훑어보면, 얻은 서열은 반드시 단조롭게 점차적으로 증가할 것이다. (중복 수치가 있는 상황을 고려하지 않는다.)
코드 첨부:

 1 /**  2  * Definition for binary tree  3  * struct TreeNode {  4  * int val;  5  * TreeNode *left;  6  * TreeNode *right;  7  * TreeNode(int x) : val(x), left(NULL), right(NULL) {}  8  * };  9  */

10 class Solution { 11 public: 12     // "fa" holds the last value that has been visited 13     // "flag" is false when it(the given binary tree or its subtree) is an invalid BST

14     void InOrder(TreeNode *root, int& fa, bool& flag) { 15         if (root->left != NULL) { 16             InOrder(root->left, fa, flag); 17  } 18         if (root->val <= fa) 19             flag = false; 20         fa = root->val; 21         if (root->right != NULL) { 22             InOrder(root->right, fa, flag); 23  } 24  } 25     bool isValidBST(TreeNode *root) { 26         if (root == NULL || root->left==NULL&&root->right==NULL) return true; 27         // initialize "fa" as INT_MIN 28         // I assume that there are no tree node's val equals to INT_MIN 29         // and it does... (test case like this doesnt exist)

30         int fa = INT_MIN; 31         bool flag = true; 32  InOrder(root, fa, flag); 33         if (flag) 34             return true; 35         else 

36             return false; 37  } 38 };

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[leetcode]_Validate Binary Search Tree

제목: 두 갈래 나무 한 그루가 합법적인지 판단한다.두 갈래 트리가 왼쪽 트리의 모든 값생각: 1. 현재 루트 노드에서 판단하여 루트 노드의 왼쪽 트리 최대값 maxLeft, 오른쪽 트리 최소값 minRight를 구...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

LeetCode --- Validate Binary Search Tree

좋은 웹페이지 즐겨찾기

LeetCode ---　Validate Binary Search Tree